Clone Graph - LeetCode Python

 Given a reference of a node in a connected undirected graph.

Return a deep copy (clone) of the graph.

Each node in the graph contains a val (int) and a list (List[Node]) of its neighbors.

class Node {
    public int val;
    public List<Node> neighbors;
}

 

Test case format:

For simplicity sake, each node's value is the same as the node's index (1-indexed). For example, the first node with val = 1, the second node with val = 2, and so on. The graph is represented in the test case using an adjacency list.

Adjacency list is a collection of unordered lists used to represent a finite graph. Each list describes the set of neighbors of a node in the graph.

The given node will always be the first node with val = 1. You must return the copy of the given node as a reference to the cloned graph.

 

Example 1:

Input: adjList = [[2,4],[1,3],[2,4],[1,3]]
Output: [[2,4],[1,3],[2,4],[1,3]]
Explanation: There are 4 nodes in the graph.
1st node (val = 1)'s neighbors are 2nd node (val = 2) and 4th node (val = 4).
2nd node (val = 2)'s neighbors are 1st node (val = 1) and 3rd node (val = 3).
3rd node (val = 3)'s neighbors are 2nd node (val = 2) and 4th node (val = 4).
4th node (val = 4)'s neighbors are 1st node (val = 1) and 3rd node (val = 3).

Example 2:

Input: adjList = [[]]
Output: [[]]
Explanation: Note that the input contains one empty list. The graph consists of only one node with val = 1 and it does not have any neighbors.

Example 3:

Input: adjList = []
Output: []
Explanation: This an empty graph, it does not have any nodes.

Example 4:

Input: adjList = [[2],[1]]
Output: [[2],[1]]

 

Constraints:

• 1 <= Node.val <= 100
• Node.val is unique for each node.
• Number of Nodes will not exceed 100.
• There is no repeated edges and no self-loops in the graph.
• The Graph is connected and all nodes can be visited starting from the given node.

"""

# Definition for a Node.

class Node:

    def __init__(self, val = 0, neighbors = None):

        self.val = val

        self.neighbors = neighbors if neighbors is not None else []

"""

class Solution:

    def cloneGraph(self, node: 'Node') -> 'Node':

        

        if not node:

            return

        

        visited = {}

        

        visited[node] = Node(node.val,[])

        from collections import deque

        

        queue = deque([node])

        

        while queue:

            n = queue.popleft()

            

            for neighbor in n.neighbors:

                if neighbor not in visited:

                    visited[neighbor] = Node(neighbor.val,[])

                    queue.append(neighbor)

                visited[n].neighbors.append(visited[neighbor])

        return visited[node]

        

TC : O(N)

SC: O(N)

Search a 2D Matrix II - Python Leetcode

 Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

• Integers in each row are sorted in ascending from left to right.
• Integers in each column are sorted in ascending from top to bottom.

Example:

Consider the following matrix:

[
  [1,   4,  7, 11, 15],
  [2,   5,  8, 12, 19],
  [3,   6,  9, 16, 22],
  [10, 13, 14, 17, 24],
  [18, 21, 23, 26, 30]
]

Using Search Space Reduction Method

Given target = 5, return true.

Given target = 20, return false.

class Solution:

    def searchMatrix(self, matrix, target):

        """

        :type matrix: List[List[int]]

        :type target: int

        :rtype: bool

        """

        if not matrix:

            return False

        rows = len(matrix)

        cols = len(matrix[0])

        

        if rows == 0 or cols ==0:

            return False

        

        row = rows-1

        col = 0

        

        while row >=0 and col < cols:

            if target == matrix[row][col]:

                return True

            elif target < matrix[row][col]:

                row -= 1

            else:

                col+=1

        return False

        Time Complexity : O(m+n)

        Space Complexity : O(1)

Search a 2D Matrix Python Leetcode

 Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

• Integers in each row are sorted from left to right.
• The first integer of each row is greater than the last integer of the previous row.

Example 1:

Input:
matrix = [
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]
target = 3
Output: true

Example 2:

Input:
matrix = [
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]
target = 13
Output: false

Main thing to note in this problem : row = pivot // cols and col = pivot % cols 

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        if not matrix or len(matrix) == 0:
            return False
        rows = len(matrix)
        cols = len(matrix[0])
        
        if rows == 1 and cols ==1:
            if target == matrix[rows-1][cols-1]:
                return True
            else:
                return False
       
        left = 0
        right = rows * cols -1
        
        while left <= right:
            pivot = left + (right-left) // 2
            
            if target == matrix[pivot // cols][pivot % cols]:
                return True
            elif target > matrix[pivot // cols][pivot % cols]:
                    left = pivot + 1
            else:
                right = pivot - 1
        return False

Time Complexity : O(logn(mn))

Space Complexity : O(1)

Search in Rotated Sorted Array - Python Leetcode

 You are given an integer array nums sorted in ascending order, and an integer target.

Suppose that nums is rotated at some pivot unknown to you beforehand (i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).

If target is found in the array return its index, otherwise, return -1.

 

Example 1:

Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4

Example 2:

Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1

Example 3:

Input: nums = [1], target = 0
Output: -1

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        if not nums:
            return -1
        
        if len(nums) == 1 and target == nums[0]:
            return 0
        
        left = 0
        right = len(nums)-1
        
        while left <= right:
            mid = left + (right-left) // 2
            
            if nums[mid] == target:
                return mid
            
            elif nums[mid] >= nums[left]:
                if target < nums[mid] and target >= nums[left]:
                    right = mid - 1
                else:
                    left = mid + 1
            else:
                if target > nums[mid] and target <= nums[right]:
                    left = mid + 1
                else:
                    right = mid - 1
        return -1
        

Complexity Analysis
Time complexity: $\mathcal{O}(\log{N})$.
Space complexity: $\mathcal{O}(1)$.

 

Find Minimum in Rotated Sorted Array II - Leetcode Python

 Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e.,  [0,1,2,4,5,6,7] might become  [4,5,6,7,0,1,2]).

Find the minimum element.

The array may contain duplicates.

Example 1:

Input: [1,3,5]
Output: 1

Example 2:

Input: [2,2,2,0,1]
Output: 0

Note:

• This is a follow up problem to Find Minimum in Rotated Sorted Array.
• Would allow duplicates affect the run-time complexity? How and why?

class Solution:

    def findMin(self, nums: List[int]) -> int:

        if not nums:

            return 

        if len(nums) == 1:

            return nums[0]

        low = 0

        high = len(nums)-1

        

        while low < high:

            mid = low + (high-low) // 2

            

            if nums[mid] < nums[high]:

                high = mid

            elif nums[mid] > nums[high]:

                low = mid + 1

            else:

                high-=1

        return nums[low]

Find Minimum in Rotated Sorted Array - Python Leetcode

 Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e.,  [0,1,2,4,5,6,7] might become  [4,5,6,7,0,1,2]).

Find the minimum element.

You may assume no duplicate exists in the array.

Example 1:

Input: [3,4,5,1,2] 
Output: 1

Example 2:

Input: [4,5,6,7,0,1,2]
Output: 0

class Solution:
    def findMin(self, nums: List[int]) -> int:
        if not nums:
            return 
        # If last element is greater than first element then no rotation happened
        if nums[len(nums)-1] >= nums[0]:
            return nums[0]
        
        left = 0
        right = len(nums)-1
        
        while left <= right:
            mid = int(left + (right-left)/2)
            
            # if mid > mid +1 there is a flunctuation in the increasing order
            if nums[mid] > nums[mid+1]:
                return nums[mid+1]
            
            #if mid-1 > mid there is a fluctuation happened in increasing order
            if nums[mid-1] > nums[mid]:
                return nums[mid]
            
            if nums[mid] > nums[0]:
                left = mid+1
            else:
                right = mid-1
                
        
Time Complexity : O(logn)

Space Complexity : O(1)

Sort Colors - Python Leetcode

 Given an array with n objects colored red, white or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white and blue.

Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

Note: You are not suppose to use the library's sort function for this problem.

Example:

Input: [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]

Follow up:

• A rather straight forward solution is a two-pass algorithm using counting sort.
  First, iterate the array counting number of 0's, 1's, and 2's, then overwrite array with total number of 0's, then 1's and followed by 2's.
• Could you come up with a one-pass algorithm using only constant space?

class Solution:

    def sortColors(self,nums: List[int]) -> None:

        """ 

        Dutch National Flag Problem

        """

        # For all idx nums[idx < p0] == 0 and idx < p0

        # For all idx idx > p2 : nums[idx > p2] == 2

        # curr is pointing current element

        

        if not nums:

            return 

        curr = p0 = 0

        p2 = len(nums) -1

        

        while curr <= p2:

            if nums[curr] == 0:

                nums[p0],nums[curr] = nums[curr],nums[p0]

                curr = curr+1

                p0 += 1 

            elif nums[curr] == 2:

                nums[curr],nums[p2] = nums[p2],nums[curr]

                p2 -= 1

            else:

                curr+=1