Sorting and Searching

DSA
Sorting and Searching
Author

Vikrant Mehta

Published

October 3, 2024

1. Longest Subsequence With Limited Sum

🎯 Understanding the Test Cases:

Test Case 1:

nums = [4, 5, 2, 1], queries = [3, 10, 21]

Explanation:

For queries[0] = 3: The longest subsequence we can take from nums is [2, 1] because \(2 + 1 = 3\), which has 2 elements. So, the answer is 2. If we add any other element, the sum becomes greater than 3. Note that in a subsequence, you can drop certain elements but the relative order stays same.

For queries[1] = 10: We can take [4, 2, 1], with a sum of \(7\), which has 3 elements. So, the answer is 3.

For queries[2] = 21: We can take the whole array [4, 5, 2, 1], with a sum of 12, which has 4 elements. So, the answer is 4.

1.1: Brute Force

  • To find out the maximum number of elements less than or equal to some number, just add the smallest numbers.
  • Sort the list first.
  • For every query in queries, find out how many elements can be added by iterating over the array nums.

Time Complexity: \(O(m \cdot n)\)

Need help with implementation? 

class Solution(object):
    def answerQueries(self, nums: List[int], queries: List[int]) -> List[int]:

        answer = [ 0 for i in range(len(queries))]
        nums.sort() # Sort so that adding smallest elements is easier

        for i in range(len(queries)):
            query = queries[i]
            index, count, total = 0, 0, 0
            
            # For every query, keep adding the smallest element to get the maximum number of 
            # elements whose total is less than or equal to that query
            while total <= query and index < len(nums):
                if total + nums[index] > query:
                    answer[i] = count
                    break
                else:
                    total += nums[index]
                    index += 1
                    count += 1
            answer[i] = count
        return answer

1.2 Prefix Sum

There’s an even better approach here. That’s with prefix sum. You would pass the test cases with the brute force approach, but it’s good to know this approach since it’s a useful concept.

  • Sort the list first.
  • Keep a prefix_sum array where ith element of it stores the sum of first i smallest elements. Notice that this array will be sorted.
  • For each queries[i], use binary search on prefix_sum to find out the largest element less than equal to queries[i]

It’s a good exercise to see why this approach would produce correct result.

Time Complexity: \(O(n \cdot \log(n))\)

Need help with implementation? 

class Solution:
    def answerQueries(self, nums: List[int], queries: List[int]) -> List[int]:
        answer = [0 for i in range(len(queries))] # O(n)
        nums.sort() # O(nlogn)
        prefix_sum = [ ] 

        # O(n)
        for i in range(len(nums)):
            prefix_sum.append(nums[0]) if i == 0 else prefix_sum.append(prefix_sum[i - 1] + nums[i])

        # O (m log n)
        for i in range(len(queries)): # O(m)
            query = queries[i]
            count = self.binarysearch(query, prefix_sum) #O(log n)
            answer[i] = count
        return answer

    def binarysearch( self,v, L):  #v = target element
        low, high = 0, len(L) - 1
        while low <= high: 
            mid = (low + high) // 2
            if L[mid ] < v:
                low = mid  + 1
            elif L[mid ] > v:
                high = mid  - 1
            else:
                return mid + 1 # return the next index than where the element was found
        return low # Returns index where the element should go if not found

2. Top K Frequent Elements

🎯 Understanding the Test Cases:

Test Case 1:

nums= [ 1, 1, 1, 2, 2, 3], k = 2

Explanation:

In this test case, the number \(1\) occurs thrice, the number \(2\) occurs twice, and the number \(3\) occurs once. Since we have to return top \(2\) most frequent numbers, we return \(1\) and \(2\). Important to note here is that the question says nothing about whether the nums array is sorted or not. If it is not explicitly given in the question, we cannot assume it.

2.1 Using Dictionaries and Sorting

  • Initialize a dictionary. For every element in nums, you count occurrences of that element. We can do this in a single pass. Plus this has the added benefit of eliminating duplicates, which we will use later. A useful library class to explore here is: from collections import Counter
  • For every unique element from the nums array, create a new 2D array where each element is of the format: [element from nums, it's count]
  • Sort this array based on the counts in descending order.
  • Pick the first k elements.

Time Complexity: \(O(m \cdot \log(m))\), where \(m\) is the number of unique elements in nums.

Need help with implementation? 


class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        counts = { } # init counts dictionary

        # count the number of occurrences for each element
        for num in nums: # O(n)
            if num in counts:
                counts[num] += 1 
            else:
                counts[num] = 1
        
        # [ [elem1, it's count], [elem2, it's count], [elem3, it's count] ]
        L = [[x, counts[x]] for x in counts.keys()] # O(m), where m = number of unique elems in nums

        # Sort in descending order based on counts
        L.sort(key=lambda x:x[1], reverse=True) # NOT O(n log n), it's O(m log m)!

        output = [ ]

        # O(k)
        # Pick out the top k elements. Note that we don't need counts. So we return L[i][0]
        for i in range(k):
            output.append(L[i][0])

        return output

3. Sort Colors

This problem is similar to what is discussed in one the practice programming assignments for this week, and we need to solve this problem in \(O(n)\) complexity.

3.1 Sort the nums in place

We can simply sort the array nums in place are return it. We can use nums.sort() for this. But the comlpexity for this will be: \(O(n \cdot \log (n))\). Can we do better?

3.2 Take Count of Colors

We know that there are only three distinct elements in the list. So can we count the occurrences for each distinct color element, and then replace the original array using these counts. For example, consider an array nums = [ 2, 0, 2, 1, 1, 0, 1]. We can keep a dictionary for counts as follows:

counts[0] = 2
counts[1] = 3
counts[2] = 2

Then for every color, we can replace nums[i] to nums[i + count] with the color.

Time Complexity: \(O(n)\)

Need help with implementation? 

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        counts = { 
            0 : 0, 
            1: 0, 
            2: 0
        }

        # O(n). Take counts for each color
        for i in range(len(nums)):
            counts[nums[i]] += 1

        index = 0

        # O(n). For each color, update the nums[i] to nums[i + count] to the color.
        for i in range(3):
            for count in range(counts[i]):
                nums[index] = i
                index += 1

4. Merge Intervals

🎯 Understanding the Test Cases:

Test Case 1:

intervals = [[1,3], [2,6], [8,10], [15,18]]

Explanation:

We start with the first interval [1, 3]. The next interval [2, 6] overlaps with [1, 3], so we merge them into [1, 6]. The next interval [8, 10] doesn’t overlap with [1, 6], so we keep it as is. The last interval [15, 18] also doesn’t overlap with any previous intervals, so we keep it as is.

Test Case 2:

intervals = [[1, 4], [2, 3], [5, 10]]

Explanation:

We start with the first interval [1, 4]. The next interval [2, 3] overlaps with [1, 4]. But note that the first interval subsumes this one. So the merged interval is: [1, 4]

The last interval [5, 10] doesn’t overlap with any previous intervals so we keep it as it is.

4.1 Sorting intervals

  • If we want to merge intervals, it would be easier if overlapping intervals come adjacently in the input list, which means… Sorting!

  • Sort based on the start of the interval.

  • For every interval, check whether start of the interval falls within the end of the merged interval

  • But we will need to consider the below corner cases:

    • One interval subsumes another, then what? This means that the second interval’s end is smaller than the first. Such as: [1, 10] and [2, 5]
    • How do you handle last interval?

We also need to keep track of the start and the end of the merged intervals.

Time Complexity: \(O(n \cdot \log(n))\)

💻 Code Implementation:
class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        if not intervals:
            return []
        
        # Sort intervals based on the start
        intervals.sort(key=lambda x: x[0])
        
        merged_intervals = []
        current_start, current_end = intervals[0]
        
        for interval in intervals[1:]:
            # Overlapping intervals, merge them
            if interval[0] <= current_end:
                current_end = max(current_end, interval[1]) # The max function is required to handle the 1st edge case
            else:
                # Non-overlapping interval found, add previous interval to result
                merged_intervals.append([current_start, current_end])

                # Update current interval
                current_start, current_end = interval
        
        # Add the last interval
        merged_intervals.append([current_start, current_end])
        
        return merged_intervals

5. Search in Rotated Sorted Array

🎯 Understanding the Test Cases:

This is a simple search problem, so the test cases are not discussed.

6. Find First and Last Position of Element in Sorted Array

🎯 Understanding the Test Cases:

Test Case 1:

nums = [5,7,7,8,8,8,10], target = 8

Explanation:

We need to find the starting and ending indices of the target number 8. In this case, 8 appears three times, so we return the range [3, 5], where index 3 is the first occurrence and index 5 is the last.

6.1 Using Binary Search

📚 Problem Overview:

Again, we need a \(\log(n)\) solution. So, we think Binary Search to come up with a solution.

💡 The Solution:

Hint:

We know binary search is fast, but it stops when we find the target. What if we keep going to find both the first and last occurrences?

Here’s how we can do it:

Leftmost Occurrence:

  • Run a binary search, but when you find 8, don’t stop! Keep searching the left half to find the first occurrence.

Rightmost Occurrence:

  • Similar idea, but now after finding 8, explore the right half to find the last occurrence.

By running two binary searches, we find both boundaries of the target range in \(O(\log n)\) time.

Need help with implementation? 

class Solution:
    def searchRange(self, nums, target):
        def findLeft(nums, target):
            leftmost_occurrence = -1
            # Finds the left most index of target number
            left, right = 0, len(nums) - 1
            while left <= right:
                mid = (left + right) // 2
                if nums[mid] < target:
                    left = mid + 1
                elif nums[mid] == target:
                    leftmost_occurrence = mid
                    right = mid - 1
                else:
                    right = mid - 1
            return leftmost_occurrence
        
        def findRight(nums, target):
            # Finds rightmost index of target
            rightmost_occurrence = -1
            left, right = 0, len(nums) - 1
            while left <= right:
                mid = (left + right) // 2
                if nums[mid] < target:
                    left = mid + 1
                elif nums[mid] == target:
                    rightmost_occurrence = mid
                    left = mid + 1
                else:
                    right = mid - 1
            return rightmost_occurrence
        
        leftmost_occurrence = findLeft(nums, target)
        rightmost_occurrence = findRight(nums, target)
        
        # Check if the target is not found
        if leftmost_occurrence == -1:
            return [-1, -1]
        return [leftmost_occurrence, rightmost_occurrence]

7. Find K Closest Elements

💻 Code Implementation:
class Solution:
    def binarysearch(self, nums, key):
        left, right = 0, len(nums) - 1
        while left <= right:
            mid = (left + right) // 2
            if nums[mid] == key:
                return mid
            elif nums[mid] > key:
                right = mid - 1
            else:
                left = mid + 1
        return left
    
    def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]:
        # Find the element
        searchindex = self.binarysearch(arr, x)
        left, right = searchindex- 1, searchindex

        # Edge cases- number is the first number in array or the last
        if searchindex < 0:
            return arr[:k]
        if searchindex > len(arr) - 1:
            return arr[k:]
        
        L = [ ]
        # Keep sliding the two pointers till you have "k" closest elems
        while len(L) < k:
            if left < 0 and right < len(arr):
                L.append(arr[right])
                right += 1
            elif right > len(arr) - 1 and left >= 0:
                L.append(arr[left])
                left -= 1
            else:
                dist1 = abs(arr[left] - x)
                dist2 = abs(arr[right] - x)
                if dist1 <= dist2:
                    L.append(arr[left])
                    left -= 1
                else:
                    L.append(arr[right])
                    right += 1
        return sorted(L)# Return the sorted "k" nums

8. Check If N and Its Double Exist

🎯 Understanding the Test Cases:

Test Case 1:

arr = [10,2,5,3]

Explanation:

In this array, arr[2] = 5 is half of arr[0] = 10. Since they’re at different indices and one is double the other, we return True.

8.1 Using Binary Search

📚 Problem Overview:

We’re looking to see if any number in the array has a double or half that’s also in the array. Binary Search can make this faster! Let’s sort the array so we can search more efficiently.

Observe:

If a number is odd, it can’t have an integer half, so we can skip it!

Pseudocode:
  • Sort the array.
  • For each number in the array:
    • Check if it’s odd or even.
    • If it’s odd, move to the next one.
    • If it’s even, binary search for its half.
    • If the half exists and indices are different, return True.

Question:

Given this problem, can you think of a case where the indices of a number and it’s double will be the same?

Need help with implementation? 


class Solution(object):
    def checkIfExist(self, arr:List[int]) -> bool:
        arr.sort() # sort array first

        for i, num in enumerate(arr):
            # If value is odd, it's half can't exist
            if num % 2 != 0:
                continue

            # Search for num / 2 in the array
            idx = self.binarysearch(arr, num / 2)

            # If num / 2 was found and indices are different return True
            if i != idx and idx != -1: 
                return True
        
        # No pair was found
        return False
    
    def binarysearch(self, L, value): 
        low = 0
        high = len(L) - 1
        while low <= high: 
            mid = (low + high) // 2
            if L[mid ] < value:
                low = mid  + 1
            elif L[mid ] > value:
                high = mid  - 1
            else:
                return mid # Found the value, so return the index at which the value was found
                
        return -1 # Couldn't find value

9. H-Index

🎯 Understanding the Test Cases:

Please refer to the Leet Code discussion on test cases for an explanation of test cases.

9.1 Using Sorting

📚 Problem Overview:

🎯 What’s the Goal?

We want to find the maximum H-index for a researcher, where H is the highest number such that at least H papers have been cited at least H times. Let’s look at the solution first, which we will unpack then.

class Solution:
    def hIndex(self, citations: List[int]) -> int:
        citations.sort(reverse=True)
        for i, citation in enumerate(citations):
            if citation <= i: 
                return i
        return len(citations)

Let’s unpack the code:

  • We sort the citations array in descending order.

  • Loop Through Each Citation:

    • i is the count of papers with at least that many citations.
    • If citation <= i, we return i as our H-index, because there are exactly i papers with at least i citations.
Tip

If this feels confusing, do spend some time in think about the if condition.

10. Capacity to Ship Packages Within D Days

Pattern Alert:

This is an important type of problem that you can solve using binary search plus sorting. In this pattern, you want to find the maximum of some minimum quantities, or the minimum of some maximum quantities. The general approach to solve these problems is:

  • Find the range of the solution
  • Binary search through the it
class Solution:
    def shipWithinDays(self, weights: List[int], days: int) -> int:
        # Take minimum possible and maximum possible answers as left and right
        left, right = max(weights), sum(weights)

        ans = right
        # Binary search like implementation
        while left <= right:
            weight_capacity = ( left + right ) // 2
            day_count = 0
            curr_load = 0

            # For a given weight_capacity, find it's answer
            for i in range(len(weights)):
                weight = weights[i]
                if curr_load + weight <= weight_capacity:

                    curr_load += weight
                    if i == len(weights) - 1:
                        day_count += 1
                else:
                    curr_load = weight
                    day_count += 1
                    if i == len(weights) - 1:
                        day_count += 1
            # Binary search logic
            if day_count > days:
                left = weight_capacity + 1
            else:
                ans = min(ans, weight_capacity)
                right = weight_capacity - 1

        return ans