Leetcode week #3: Binary Search and Sliding Window (pt 1)

Jul 22, 2024 | monday 5:25 pm

This series will be mainly focused for my own accountability and reference, as well as anyone who wants to follow my journey to becoming a better problem solver. Each week, I will highlight problems that I thought was interesting or difficult. Additionally, other problems that I solved and their solutions are listed below.

🟡 Longest Substring without Repeating Characters
🟢 Best Time to Buy and Sell Stock
🟢 Binary Search
🟡 Search a 2D Matrix
🟡 Koko Eating Bananas
🟡 Find Minimum in Rotated Sorted Array
🟡 Time Based Key-Value Store
🟡 Longest Repeating Character Replacement
🟡 Permutation in String

Longest Substring without Repeating Characters

MediumSliding-window

Try it yourself here!

This problem has long been one of the most challenging for me. I’ve always jumped straight to solving the most optimal solution without fully grasping the concept of a sliding window.

Problem Statement: The goal is to find the longest substring that contains only unique characters (no duplicates).

Example:

s = “abcabcbb” The answer is 3, with any permutation of “abc”.

Basic Solution:

Use a sliding window technique
Utilize a set to keep track of unique characters
Employ left and right pointers to manage the window

Algorithm:

Loop through the array
For each new character:
- Check if it’s in the set
- If so, move the left pointer until the character is no longer in the set
- Remove subsequent characters before it
Calculate the length of the new substring
Add the new character to the set

Complexity:

Time: O(2n) - Worst case, we add and remove every character from the set twice
Space: O(n) - We use a set to store the characters

Optimal Solution:

Use a map instead of a set
Immediately find the left duplicate character position

Algorithm:

Use a map to store character positions
When encountering a duplicate:
- Shift the left pointer to the position stored in the map
- Consider edge cases where the left pointer is already past the stored position

Example:

mp = { a : 1, b : 3} l = 2 r = 3

s = “abba” ^ In this case, ‘a’ is in the map at position 1, but the left pointer (l) is at 2. We keep the higher index to ensure we skip all duplicates.

Complexity:

Time: O(n) - Each index is only looked at once
Space: O(n) - We use a map to store the characters

By using a map, we can optimize the solution and reduce the time complexity from O(2n) to O(n).

## Solution 1
def lengthOfLongestSubstring(self, s: str) -> int:
    charSet = set()
    l = 0
    maxLen = 0
    for r in range(len(s)):
        while s[r] in charSet:
            charSet.remove(s[l])
            l += 1
        maxLen = max(maxLen, r - l + 1)
        charSet.add(s[r])

    return maxLen

## Solution 2: Optimal
def lengthOfLongestSubstring(self, s: str) -> int:
    charMap = {}
    l = 0
    res = 0
    for r in range(len(s)):
        if s[r] in charMap:
            l = max(charMap[s[r]], l)
        charMap[s[r]] = r + 1
        res = max(res, r - l + 1)
    return res

Best Time to Buy and Sell Stock

EasySliding-window

Try it yourself here!

def maxProfit(self, prices: List[int]) -> int:
     min_price = prices[0]
     max_profit = 0
     for p in prices[1:]:
         max_profit = max(p - min_price, max_profit)
         min_price = min(min_price, p)
     return max_profit

Complexity:

Time: O(n) - Each index is only looked at once
Space: O(1) - Constant space is used to obtain the answer

Binary Search

EasyBinary-search

Try it yourself here!

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

Complexity:

Time: O(log n) - Each search cuts the solution space in half
Space: O(1) - Constant space is used to find the solution

Search a 2D Matrix

MediumBinary-search

Try it yourself here!

def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
    # strategy: treat the 2d matrix as 1d
    m = len(matrix)
    n = len(matrix[0])
    l, r = 0, m * n - 1
    while l <= r:
     mid = (l + r) // 2
     row = (mid // n)
     col = (mid % n)
     if matrix[row][col] == target:
         return True
     elif matrix[row][col] > target:
         r = mid - 1
     else:
         l = mid + 1

    return False

Complexity:

Time: O(log (m * n) - Each search cuts the solution space in half
Space: O(1) - Constant space is used to find the solution

Koko Eating Bananas

MediumBinary-search

Try it yourself here!

def minEatingSpeed(self, piles: List[int], h: int) -> int:
     def canEat(k):
         hours = 0
         for p in piles:
             hours += math.ceil(p / k)
         return hours <= h

     lo, hi = 1, max(piles)
     while lo <= hi:
         mid = (lo + hi) // 2
         if canEat(mid):
             hi = mid - 1
         else:
             lo = mid + 1
     return lo

Complexity:

Time: O(n * log (m) - Where n is the length of piles and m is the maximum bananas. Each search cuts the banana space in half
Space: O(1) - Constant space is used to find the solution

Find Minimum in Rotated Sorted Array

MediumBinary-search

Try it yourself here!

def findMin(self, nums: List[int]) -> int:
     if len(nums) == 1:
         return nums[0]
     
     l, r = 0, len(nums) - 1
     if nums[r] > nums[0]:
         return nums[0]
     while l <= r:
         mid = (l + r) // 2
         if nums[mid] > nums[mid + 1]:
             return nums[mid + 1]
         if nums[mid - 1] > nums[mid]:
             return nums[mid]
         if nums[mid] > nums[0]:
             l = mid + 1
         else:
             r = mid - 1

Complexity:

Time: O(log n) - Each search cuts the solution space in half, where n is the size of nums.
Space: O(1) - Constant space is used to find the solution

Time Based Key-Value Store

MediumBinary-search

Try it yourself here!

class TimeMap:
    def __init__(self):
        self.key_time_map = {}

    def set(self, key: str, value: str, timestamp: int) -> None:
        if key not in self.key_time_map:
            self.key_time_map[key] = []
        self.key_time_map[key].append([value, timestamp])
        

    def get(self, key: str, timestamp: int) -> str:
        if key not in self.key_time_map:
            return ""
        time_value_list = self.key_time_map[key]
        left, right = 0, len(time_value_list) - 1
        while left <= right:
            mid = (left + right) // 2
            if time_value_list[mid][1] == timestamp:
                return time_value_list[mid][0]
            elif time_value_list[mid][1] > timestamp:
                right = mid - 1
            else:
                left = mid + 1
        return time_value_list[left - 1][0] if left > 0 else ""

Complexity:

Time: O(log (n)) - Where the time comes from the get function to find the timestamp.
Space: O(n) - Where n is the size of the hashmap.

Longest Repeating Character Replacement

MediumSliding-window

Try it yourself here!

def characterReplacement(self, s: str, k: int) -> int:
     l = 0
     maxLen = 0
     mp = {}
     for r in range(len(s)):
         mp[s[r]] = mp.get(s[r], 0) + 1
         while l < len(s) and r - l + 1 - max(mp.values()) > k:
             mp[s[l]] -= 1
             l += 1
         maxLen = max(maxLen, r - l + 1)
     return maxLen

Complexity:

Time: O(n^2) - Time to traverse the string and calculate the current max value.
Space: O(n) - Where n is the size of the hashmap.

Permutation in String

MediumSliding-window

Try it yourself here!

def checkInclusion(self, s1: str, s2: str) -> bool:
     cnt1 = Counter(s1)
     cnt2 = Counter(s2[:len(s1)])
     l = 0
     for r in range(len(s1), len(s2)):
         if cnt1 == cnt2:
             return True
         cnt2[s2[l]] -= 1
         cnt2[s2[r]] += 1
         l += 1
     return cnt1 == cnt2

Complexity:

Time: O(n) - Where n is the length of s2.
Space: O(2 * n) - Hashmap needed for both strings.