Secondary loop BS¶

Bisect derivatives¶

167. Two Sum II - Input Array Is Sorted (Medium)¶

Solution

While binary searching, we only need to search from the index i until last element.

Analysis

Time Complexity: O(Nlog****_N_**)**

where:

N is the length of the array

Space Complexity: O(1)

def twoSum(self, numbers: List[int], target: int) -> List[int]:
    for i in range(len(numbers)):
        find = target - numbers[i]
        j = self.bisect_left(numbers, find, lo=i + 1, hi=len(numbers))
        if j < len(numbers) and numbers[j] == find:
            return [i + 1, j + 1]
    return [-1, -1]

1855. Maximum Distance Between a Pair of Values (Medium)¶

Solution

Both arrays are sorted in descending order.

By looping over first array (say nums1[i]) and finding the insert position (say j) in second array, should return how many numbers in second array are greater than the element of first array.

To find the insert position, we should be using bisect_right_rev.

But we are only concerned with i <= j, hence we can subtract i from j. And j - i is the distance between the numbers. Keep track of maximum distance, and return the maximum distance.

Analysis

Time Complexity: \(\mathcal{O}(m\cdot\log n)\)

where:

\(m\) is the length of nums1
\(n\) is the length of nums2

We Iterate over nums1 and perform binary search over nums2 which takes \(\mathcal{O}(\log n)\)

Space Complexity: \(\mathcal{O}(1)\)

def maxDistance(self, nums1: List[int], nums2: List[int]) -> int:
    maxi = 0
    for i, a in enumerate(nums1):
        j = self.bisect_right_rev(nums2, a)
        maxi = max(maxi, j - i - 1)
    return maxi

Solution

Both arrays are sorted in descending order.

By looping over first array (say nums1[i]) and finding the insert position (say j) in second array, should return how many numbers in second array are greater than the element of first array.

But we reverse the second array here. Also we are only concerned with i <= j, hence we can subtract i from len(nums2) - j. So, the distance would be len(nums2) - j - i - 1. Keep track of maximum distance, and return the maximum distance.

Analysis

Time Complexity: \(\mathcal{O}(m\cdot\log n)\)

where:

\(m\) is the length of nums1
\(n\) is the length of nums2

We Iterate over nums1 and perform binary search over nums2 which takes \(\mathcal{O}(\log n)\)

Space Complexity: \(\mathcal{O}(1)\)

Note that, reversing the array will take \(\mathcal{O}(1)\)

def maxDistance(self, nums1: List[int], nums2: List[int]) -> int:
    maxi = 0
    nums2.reverse()
    for i, a in enumerate(nums1):
        j = self.bisect_left(nums2, a)
        maxi = max(maxi, len(nums2) - j - i - 1)
    return maxi

1346. Check If N and Its Double Exist (Easy)¶

Solution

Loop over the array with element arr[i], binary search for its double 2 * arr[i] in the same array.

Note that, keep track of zeros, and if there are more than 2 zeros, return True.

Analysis

Time Complexity: \(\mathcal{O}(n\cdot\log n)\)

where:

\(n\) is the length of the array

It takes \(\mathcal{O}(n)\) to loop over the array and \(\mathcal{O}(\log n)\) to binary search for its double.

Space Complexity: \(\mathcal{O}(1)\)

def checkIfExist(self, arr: List[int]) -> bool:
    arr.sort()
    zeros = 0
    for num in arr:
        if num == 0:
            zeros += 1
        else:
            index = self.bisect_left(arr, 2 * num)
            if index < len(arr) and arr[index] == 2 * num:
                return True
    return zeros >= 2

Bisect derivatives in 2D Matrix¶

1351. Count Negative Numbers in a Sorted Matrix (Easy)¶

Solution

Search for last 0 , and not the first. It doesn’t matter if 0 is not present in the array, bisect_right_rev will point to where 0 is supposed to be inserted. Or where the negative numbers start (if exists).

Analysis

Time Complexity: O(Nlog****_M_**)**

where:

N is the number of rows
M is the number of columns

Space Complexity: O(1)

def countNegatives(self, grid: List[List[int]]) -> int:
    negatives = 0
    for row in range(len(grid)):
        index = self.bisect_right_rev(grid[row], 0)
        print(index, grid[row])
        negatives += len(grid[row]) - index
    return negatives

1337. The K Weakest Rows in a Matrix (Easy)¶

Solution

Ref: 1337. The K Weakest Rows in a Matrix (Easy)

Find the total number of 1’s, which is soldiers for each row.

We could simply insert all the pairs of (soldiers, row) and sorted it. But here we are using priority queue.

Python provides min heap, but to get max heap we need to multiply elements with -1. Also, we need to multiply again to get the original number and finally we need to reverse the order.

Since, we only need max k elements, we can trim off during insertion.

Analysis

Time Complexity: O(Nlog****_Mk_**)**

where:

N is total number of rows
M is total number of columns

The total time complexity is NlogM + Nlogk = O(NlogMk)

Space Complexity: O(1)

def kWeakestRows(self, mat: List[List[int]], k: int) -> List[int]:
    max_heap = []
    for row in range(len(mat)):
        soldiers = self.bisect_left_rev(mat[row], 0)
        # Put the strength/index pairs into a priority queue.
        entry = (-soldiers, -row)
        heapq.heappush(max_heap, entry)
        if len(max_heap) > k:
            heapq.heappop(max_heap)
    ans = []
    # Pull out and return the indexes of the smallest k entries.
    # Don't forget to convert them back to positive numbers!
    while max_heap:
        ans.append(-heapq.heappop(max_heap)[1])
    return ans[::-1]  # Reverse, as the indexes are around the wrong way.

Intersection¶

349. Intersection of Two Arrays (Easy)¶

Solution

Sorting both arrays takes time O(N * logN)

Iterate over first array, and search for that element in the second array using binary search.

To avoid duplicate elements, we wanted to sort first array, or the array we iterate using for loop.

Analysis

Time Complexity: O(Nlog****_M_**)**

where:

N is the length of the first array
M is the length of the second array

Space Complexity: O(sort)

def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
    nums1.sort()
    nums2.sort()
    ans = []
    prev = None
    for num in nums1:
        if num == prev:
            continue
        index = self.bisect_left(nums2, num)
        if index < len(nums2) and nums2[index] == num:
            ans.append(num)
        prev = num
    return ans

350. Intersection of Two Arrays II (Easy)¶

Solution

Sorting both arrays takes time O(N * logN)

Iterate over first array, and search for that element in the second array using binary search.

To avoid duplicate elements, we wanted to sort first array, or the array we iterate using for loop.

But, we since we need to pop the element, it takes O(M) for each element in iteration, hence worst case would be O(NM).

Analysis

Time Complexity: O(NM)

where:

N is the length of the first array
M is the length of the second array

Space Complexity: O(sort)

def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
    nums1.sort()
    nums2.sort()
    ans = []
    for num in nums1:
        index = self.bisect_left(nums2, num)
        print(index, nums2)
        if 0 <= index < len(nums2) and nums2[index] == num:
            nums2.pop(index)
            ans.append(num)
    return ans

1198. Find Smallest Common Element in All Rows (Medium)¶

Solution

The first loop loops over first row O(M)), for each number if the same number is present in all other rows, return that number.

The second loop loops over all rows (except first) O(N)), and try to binary search O(logM)) for the number in all rows.

The first number in all rows, will be the minimum common number.

Analysis

Time Complexity: O(NMlog****_M_**)**

where:

N is the number of rows
M is the number of columns

Space Complexity: O(1)

def smallestCommonElement(self, mat: List[List[int]]) -> int:
    for num in mat[0]:
        found = True
        for row in range(1, len(mat)):
            index = self.bisect_left(mat[row], num)
            if not (index < len(mat[row]) and mat[row][index] == num):
                found = False
                break
        if found:
            return num
    return -1

1213. Intersection of Three Sorted Arrays (Easy)¶

Solution

Similar to 1198. Find Smallest Common Element in All Rows (Medium), but we need to extend.

Here, instead of returning the first common element, we need to add all common elements into an array and return the array.

Analysis

Time Complexity: O(NMlog****_M_**)**

where:

N is the number of rows
M is the number of columns

Space Complexity: O(1)

def arraysIntersection(
    self, arr1: List[int], arr2: List[int], arr3: List[int]
) -> List[int]:
    mat = [arr1, arr2, arr3]
    ans = []
    for num in mat[0]:
        found = True
        for row in range(1, len(mat)):
            index = self.bisect_left(mat[row], num)
            if not (index < len(mat[row]) and mat[row][index] == num):
                found = False
                break
        if found:
            ans.append(num)
    return ans

Custom Bisect¶

1428. Leftmost Column with at Least a One (Medium)¶

Solution

Got to find the minimum column of element 1 in all rows.

When progressing through rows, the max column we need to go through is the min_col because, we don’t have to search beyond min_col since we have already found 1 at min_col in previous rows.

Analysis

Time Complexity: O(Nlog****_M_**)**

where:

N is the total number of rows
M is the total number of columns

Space Complexity: O(1)

def leftMostColumnWithOne(self, binaryMatrix: "BinaryMatrix") -> int:
    def bisect_left(row):
        lo, hi = 0, n - 1
        target = 1
        while lo < hi:
            mid = lo + (hi - lo) // 2
            if binaryMatrix.get(row, mid) < target:
                lo = mid + 1
            else:
                hi = mid
        return lo

    m, n = binaryMatrix.dimensions()
    mini = n
    for row in range(m):
        if binaryMatrix.get(row, n - 1) != 0:
            first_one = bisect_left(row)
            mini = min(mini, first_one)
    return mini if mini != n else -1