Arrays

• Linear Search Vs Binary Search
  • Linear Search: Use when array is unsorted
  • Binary Search: Use when array is sorted

def linear_search(arr:List, search: int) -> int:
    for index, item in enumerate(arr):
        if item == search:
            return index
    return -1

def binary_search(arr: List, target: int) -> int:
    left = 0
    right = len(arr) - 1

    while (left <= right):
        mid = (left+right)//2

        if target == arr[mid]:
            return mid
        elif target < arr[mid]:
            right = mid-1
        elif target > arr[mid]:
            left = mid + 1
    return -1

• Sorting Algorithms CheatSheet

# 📘 Sorting Algorithms Cheat Sheet

| Algorithm        | Best Time     | Average Time  | Worst Time    | Space       | Stable | In-place |
|------------------|---------------|---------------|---------------|-------------|--------|----------|
| **Bubble Sort**  | O(n)          | O(n²)         | O(n²)         | O(1)        | ✅     | ✅       |
| **Selection Sort | O(n²)         | O(n²)         | O(n²)         | O(1)        | ❌     | ✅       |
| **Insertion Sort | O(n)          | O(n²)         | O(n²)         | O(1)        | ✅     | ✅       |
| **Merge Sort**   | O(n log n)    | O(n log n)    | O(n log n)    | O(n)        | ✅     | ❌       |
| **Quick Sort**   | O(n log n)    | O(n log n)    | O(n²)         | O(log n)*   | ❌     | ✅       |
| **Heap Sort**    | O(n log n)    | O(n log n)    | O(n log n)    | O(1)        | ❌     | ✅       |
| **Counting Sort**| O(n + k)      | O(n + k)      | O(n + k)      | O(k)        | ✅     | ❌       |
| **Radix Sort**   | O(nk)         | O(nk)         | O(nk)         | O(n + k)    | ✅     | ❌       |
| **Bucket Sort**  | O(n + k)      | O(n + k)      | O(n²)         | O(n + k)    | ✅     | ❌       |
| **Tim Sort**     | O(n)          | O(n log n)    | O(n log n)    | O(n)        | ✅     | ✅       |

🔹 Notes:
- `n` = number of elements
- `k` = range of input (for Counting/Radix/Bucket Sort)
- `*` Quick Sort space complexity is O(log n) due to recursion stack
- In sorting algorithms, stability refers to whether the algorithm preserves the relative order of equal elements.
- An in-place algorithm sorts the data without using extra space (or uses only a small, constant amount of additional memory).

• Array Vs Subarray Vs Subsequence

| Term           | Definition                                                   | Contiguous? | Order Maintained? | Example from `[1, 2, 3, 4]`              |
|----------------|--------------------------------------------------------------|-------------|-------------------|------------------------------------------|
| **Array**      | The entire collection of elements                            | Yes         | Yes               | `[1, 2, 3, 4]`                           |
| **Subarray**   | A continuous part (slice) of the array                       | Yes         | Yes               | `[2, 3]`, `[1, 2, 3]`                    |
| **Subsequence**| Any ordered sequence from the array without being contiguous | No          | Yes               | `[1, 3, 4]`, `[2, 4]`, `[1, 2, 3, 4]`    |

---

### Key Points:
- **Subarray = contiguous slice of the array.**
- **Subsequence = ordered elements, possibly skipping some elements.**
- **Array = the full list itself.**

Pattern 1: Two Pointer Approach

Easy : Reverse an Array In-place

Problem: Given an array, reverse its elements in-place. Example: Input: [1, 2, 3, 4, 5] -> Output: [5, 4, 3, 2, 1]

arr = [1, 2, 3, 4, 5]
start = 0
end = len(arr) - 1

while (start <= end):
    arr[start], arr[end] = arr[end], arr[start]
    start += 1
    end -= 1

print(arr)

Approach: Use one pointer at the start and one at the end. Swap elements and move pointers towards the center until they meet or cross.
Time Complexity: O(n)

Medium: Find a Pair with a Given Sum in a Sorted Array

Problem: - Given a sorted array of integers and a target sum, and if there exists a pair of elements that sum up to the target. - Return their indices or true/false. - Example: Input: arr = [2, 7, 11, 15], target = 9 -> Output: [0, 1] or true

from typing import List


def check_sum(arr: List, target_sum: int) -> List | bool:
    left = 0
    right = len(arr) - 1

    while left <= right:
        current_sum = arr[left] + arr[right]
        if current_sum > target_sum:
            right -= 1
        elif current_sum < target_sum:
            left += 1
        elif current_sum == target_sum:
            return [left, right]
    return False


arr = [2, 7, 11, 15]
target_sum = 11
result = check_sum(arr=arr, target_sum=target_sum)
print(result)

Approach: Use two pointers, left at the beginning and right at the end. 
If arr[left] + arr[right] is less than target, increment left. If greater, decrement right. If equal, you found the pair.

Time Complexity: O(n)

Hard: 3 Sum

• Given an integer array nums, find all the unique triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and their sum is equal to zero (nums[i] + nums[j] + nums[k] == 0).

• Key Constraints:

  • The indices i, j, and k must be distinct.
  • The solution set must not contain duplicate triplets. This means that even if different indices produce the same set of three numbers, that triplet should only be included once in the output.
  • For example, if nums = [-1, 0, 1, 2, -1, -4], the triplet [-1, 0, 1] can be formed in multiple ways, but it should only appear once in the final result.

• Brute Force Solution (v1)

def get_unique_triplet(arr: list) -> list[int]:
    n = len(arr)
    triplet_keys = set()
    result = []

    for i in range(0, n):
        for j in range(i + 1, n):
            for k in range(j + 1, n):
                current_sum = arr[i] + arr[j] + arr[k]
                if current_sum == 0 and (i != j and i != k and j != k):
                    triplet = [arr[i], arr[j], arr[k]]
                    key = "".join([str(item) for item in set(triplet)])
                    if key not in triplet_keys:
                        result.append(triplet)
                        triplet_keys.add(key)

    return result

arr = [-1, 0, 1, 2, -1, -4]
print(get_unique_triplet(arr))

Time Complexity:  
    - Outer loop: O(n)  
    - Middle loop: O(n)  
    - Inner loop: O(n)  
    - Total: O(n³)

Space Complexity: O(k)  
    - triplet_keys set → O(k)  
    - result list → O(k)  
    - k = number of unique triplets found (worst case k ≤ C(n,3) = O(n³))

---

• Two Pointer with Set for Duplicate Removal (v2)

def get_unique_triplet_v2(arr: list) -> list[int]:
    n = len(arr)
    arr.sort()
    triplet_keys = set()
    result = []

    for i in range(0, n):
        j = i + 1
        k = n - 1
        while j < k:
            current_sum = arr[i] + arr[j] + arr[k]
            if current_sum == 0 and (i != j and i != k and j != k):
                triplet = [arr[i], arr[j], arr[k]]
                key = "".join([str(item) for item in set(triplet)])
                if key not in triplet_keys:
                    result.append(triplet)
                    triplet_keys.add(key)
                j += 1
                k -= 1
            elif current_sum < 0:
                j += 1
            else:
                k -= 1
    return result

Time Complexity:  
    - Sorting: O(n log n)  
    - Outer loop: O(n)  
    - Two-pointer scan per i: O(n) → O(n²) total  
    - Overall: O(n²) (sorting is smaller term)

Space Complexity: O(k)  
    - triplet_keys set → O(k)  
    - result list → O(k)  
    - k = number of unique triplets found (worst case k ≤ O(n²))

---

• Two Pointer with In-Loop Duplicate Skipping (v3)

def get_unique_triplet_v3(arr: list) -> list[int]:
    n = len(arr)
    arr.sort()
    result = []

    for i in range(0, n):
        if i > 0 and arr[i] == arr[i - 1]:
            continue
        j = i + 1
        k = n - 1
        while j < k:
            current_sum = arr[i] + arr[j] + arr[k]
            if current_sum == 0 and (i != j and i != k and j != k):
                result.append([arr[i], arr[j], arr[k]])
                j += 1
                k -= 1
                while j < k and arr[j] == arr[j - 1]:
                    j += 1
                while j < k and arr[k] == arr[k + 1]:
                    k -= 1
            elif current_sum < 0:
                j += 1
            else:
                k -= 1
    return result

Time Complexity:  
    - Sorting: O(n log n)  
    - Outer loop: O(n)  
    - Two-pointer scan per i: O(n) → O(n²) total  
    - Overall: O(n²)

Space Complexity: O(k)  
    - result list → O(k) 

Pattern 2: Sliding Window

Easy: Maximum Sum Subarray of Size K

• Problem: Given an array of positive numbers and a positive integer k, find the maximum sum of any contiguous subarray of size k.
• Example: Input: arr = [1, 4, 2, 10, 2, 3, 1, 0, 20], K = 3 -> Output: 21 (from subarray [1, 0, 20])
• Approach: Calculate the sum of the first k elements. Then, slide the window: subtract the element leaving the window and add the new element entering the window. Keep track of the maximum sum found.

Feature	Contiguous	Subsequence
Skip allowed?	❌ No	✅ Yes
Order preserved?	✅ Yes	✅ Yes
Defined by	Start index & end index	Selection of elements in order
Example	[2, 3, 4]	[2, 4]

from typing import List

arr = [1, 4, 2, 10, 2, 3, 1, 0, 20]
k = 3

def max_sum_subarray(arr: List, k: int):
    left = 0
    right = k - 1
    max_sum = -1
    while (right < len(arr)):
        current_sum = sum([arr[i] for i in range(left, right+1)])

        max_sum = max(max_sum, current_sum)

        left += 1
        right += 1

    return max_sum

Time Complexity: O(n - k) ≈ O(n)
Space Complexity: 0(1)

Medium: Longest Substring with K Distinct Characters

• Problem: Given a string (or character array) and an integer k, find the length of the longest substring in it that contains no more than k distinct characters.
• Example: Input: str = "araaci", K = 2 -> Output: 4 (for "araa")
• Approach: Use a sliding window and a hash map to keep track of character frequencies. Expand the window until it contains more than k distinct characters, then shrink from the left until the condition is met again.

def longest_substring_with_k_distinct(s: str, k: int) -> int:
    if k == 0 or not s:
        return 0

    left = 0
    right = 0
    char_freq = {}
    max_len = 0

    for right in range(len(s)):
        char = s[right]
        char_freq[char] = char_freq.get(char, 0) + 1

        while len(char_freq) > k:
            left_char = s[left]
            char_freq[left_char] -= 1

            if char_freq[left_char] == 0:
                del char_freq[left_char]
            left += 1

        max_len = max(max_len, right-left+1)

    return max_len

Time Complexity: 0(n)
Space Complexity: 0(k)

Hard: Minimum Window Substring

• Problem: Given two strings s and t, find the minimum window substring of s that contains all the characters of t.
• Example: Input: s = "ADOBECODEBANC", t = "ABC" -> Output: "BANC"
• Approach: Use a sliding window and a frequency map for characters in t. Expand the window to include all characters from t, then try to shrink it from the left while maintaining the condition.

def initialize_required_char_freq(string: str):
    frequency_map = {}
    for char in string:
        frequency_map[char] = frequency_map.get(char, 0) + 1
    return frequency_map

def is_minimum_char_freq_satisfied(current_freq: dict, required_freq: dict):
    for char, freq in required_freq.items():
        if current_freq.get(char, 0) < freq:
            return False
    return True

def min_window_substring(s: str, t: str) -> str:
    left_pointer = 0
    string_length = len(s)
    current_freq = {}
    required_freq = initialize_required_char_freq(t)
    best_window_indices = [0, 0]
    best_window_length = float("inf")

    for right_pointer in range(string_length):
        current_char = s[right_pointer]
        current_freq[current_char] = current_freq.get(current_char, 0) + 1

        while is_minimum_char_freq_satisfied(current_freq, required_freq):
            current_window_size = right_pointer - left_pointer + 1
            if current_window_size < best_window_length:
                best_window_length = current_window_size
                best_window_indices = [left_pointer, right_pointer + 1]

            # shrink window from the left
            left_char = s[left_pointer]
            current_freq[left_char] -= 1
            if current_freq[left_char] == 0:
                del current_freq[left_char]
            left_pointer += 1

    return "" if best_window_length == float("inf") else s[best_window_indices[0]:best_window_indices[1]]

Time: O(|s|) — Each character visited at most twice (once by right pointer, once by left pointer).
Space: O(|s| + |t|) in worst case (frequency maps). If fixed alphabet (like ASCII), O(1).

Pattern 3: Prefix Sum / Suffix Sum

Easy: Range Sum Query - Immutable

• Problem: Given an integer array nums, handle multiple queries of the form sumRange(i, j), which returns the sum of elements between indices i and j (inclusive).
• Example: Input: nums = [-2, 0, 3, -5, 2, -1], sumRange(0, 2) -> Output: 1 ((−2)+0+3=1)
• Approach: Create a prefix sum array P where P[i] is the sum of nums[0] through nums[i-1]. Then sumRange(i, j) is simply P[j+1] - P[i].

nums = [-2,  0,  3,  -5,  2,  -1]

P[0] = 0
       (No elements yet → sum = 0)

P[1] = P[0] + nums[0]
     = 0 + (-2)
     = -2
       (Covers: -2)

P[2] = P[1] + nums[1]
     = -2 + 0
     = -2
       (Covers: -2, 0)

P[3] = P[2] + nums[2]
     = -2 + 3
     = 1
       (Covers: -2, 0, 3)

P[4] = P[3] + nums[3]
     = 1 + (-5)
     = -4
       (Covers: -2, 0, 3, -5)

P[5] = P[4] + nums[4]
     = -4 + 2
     = -2
       (Covers: -2, 0, 3, -5, 2)

P[6] = P[5] + nums[5]
     = -2 + (-1)
     = -3
       (Covers: -2, 0, 3, -5, 2, -1)

def build_prefix(arr: list[int]) -> list[int]:
    n = len(arr)
    prefix_sum = [0] * (n+1)
    for i in range(n):
        prefix_sum[i+1] = prefix_sum[i] + arr[i]
    return prefix_sum

def sumRange(prefix_sum, i, j):
    return prefix_sum[j + 1] - prefix_sum[i]


arr = [-2,  0,  3,  -5,  2,  -1]
print(sumRange(
    prefix_sum=build_prefix(arr=arr),
    i=0,
    j=4
))

**Time Complexity**
- `build_prefix`: O(n)
- `sumRange`: O(1)
- Overall (n elements, q queries): O(n + q)

**Space Complexity**
- Extra space for prefix array: O(n)
- Query space: O(1)

Medium: Subarray Sum Equals K

• Problem: Given an array of integers nums and an integer k, return the total number of continuous subarrays whose sum equals k.
• Example: Input: nums = [1, 1, 1], k = 2 -> Output: 2 (subarrays [1,1] from index 0 and [1,1] from index 1)
• Approach: Use prefix sums and a hash map. Maintain a running sum. For each element, check if current_sum - k exists in the hash map. If it does, add its frequency to the count. Store current_sum and its frequency in the map.

def build_prefix_sum(arr:list[int]) -> list[int]:
    n = len(arr)
    prefix_sum: list[int] = [0] * (n + 1)

    for i in range(n):
        prefix_sum[i+1] = prefix_sum[i] + arr[i]
    return prefix_sum

def sumRange(prefix_sum: list[int], i: int, j: int) -> int:
    return prefix_sum[j + 1] - prefix_sum[i]

def get_subarray_sum_count(arr: list[int], target_sum: int) -> int:
    n = len(arr)
    prefix_sum = build_prefix_sum(arr=arr)
    count = 0

    for i in range(n):
        for j in range(i+1, n):
            if sumRange(prefix_sum=prefix_sum, i=i, j=j) == target_sum:
                count += 1
    return count

# Example
arr = [1, 1, 1]
k = 2
print(get_subarray_sum_count(arr, k))  # Output: 2

Hard: Find Pivot Index / Equilibrium Index

• Problem: Given an array of integers nums, calculate the pivot index of this array. The pivot index is the index where the sum of all the numbers strictly to the left of the index is equal to the sum of all the numbers strictly to the right of the index.
• Example: Input: nums = [1, 7, 3, 6, 5, 6] -> Output: 3 (At index 3, left sum 1+7+3=11, right sum 5+6=11)
• Approach: Calculate the total sum of the array. Iterate through the array, maintaining a left_sum. For each element, check if left_sum equals total_sum - left_sum - current_element.

def build_prefix_sum(arr:list[int]) -> list[int]:
    n = len(arr)
    prefix_sum: list[int] = [0] * (n + 1)

    for i in range(n):
        prefix_sum[i+1] = prefix_sum[i] + arr[i]
    return prefix_sum

def sumRange(prefix_sum: list[int], i: int, j: int) -> int:
    return prefix_sum[j + 1] - prefix_sum[i]

def get_pivot_element(arr: list[int]) -> int:
    n = len(arr)
    prefix_sum = build_prefix_sum(arr=arr)

    for k in range(1, n):
        left_sum = sumRange(prefix_sum=prefix_sum, i=0, j=k-1)
        right_sum = sumRange(prefix_sum=prefix_sum, i=k+1, j=n-1)

        if left_sum == right_sum:
            return arr[k]
    return -1

arr = [1, 7, 3, 6, 5, 6]
print(get_pivot_element(arr=arr))

Time Complexity
build_prefix → O(n)
Loop through each index → O(n)
Each sumRange call is O(1) (because we just do subtraction from the prefix array).
Total: O(n) + O(n) = O(n)

Space Complexity
Prefix sum array: size n+1 → O(n)
A few variables → O(1) extra
Total: O(n)

Pattern 4: Sorting and Searching

Medium: Merge Intervals

• Problem: Given an array of intervals where intervals[i] = [start_i, end_i], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.
• Example: [[2,3], [6, 9], [7, 10], [1,5]] => [[1, 5], [6, 10]]

Step1: Sort the invervals based on starting number
Step2: Check between two interval [a,b] [c,d] if b>=c => [a,d]
Step3: If overlapping found, the set the last interval 1st index to be max of both interval 1st index number

def merge_interval(num: list[list[int]]):
    if not num:
        return []

    num.sort(key=lambda x: x[0])
    merged_interval = [num[0]]

    for current_start, current_end in num[1:]:
        last_start, last_end = merged_interval[-1]

        if last_end >= current_start:
            merged_interval[-1][1] = max(last_end, current_end)
        else:
            merged_interval.append([current_start, current_end])
    return merged_interval

Pattern 5: In-place Operations / Modifications

Easy: Remove Duplicates from Sorted Array In-place

• Problem: Given a sorted array nums, remove the duplicates in-place such that each unique element appears only once. The relative order of the elements should be kept the same.
• Example: Input: nums = [1,1,2] -> Output: 2, with nums becoming [1,2,_] (underscores denote irrelevant values beyond the new length).
• Approach: Use two pointers: one to iterate through the array, and another to keep track of the position of the next unique element.

Given array: [1, 1, 2, 2, 3, 3]

Step 1:
i = 1
Compare arr[1] = 1 with arr[0] = 1
They are equal, no change
unique_pos = 1

Step 2:
i = 2
Compare arr[2] = 2 with arr[1] = 1
They are different
Place arr[2] (2) at arr[unique_pos] -> arr[1] = 2
Increment unique_pos to 2
Array now: [1, 2, 2, 2, 3, 3]

Step 3:
i = 3
Compare arr[3] = 2 with arr[2] = 2
They are equal, no change
unique_pos = 2

Step 4:
i = 4
Compare arr[4] = 3 with arr[3] = 2
They are different
Place arr[4] (3) at arr[unique_pos] -> arr[2] = 3
Increment unique_pos to 3
Array now: [1, 2, 3, 2, 3, 3]

Step 5:
i = 5
Compare arr[5] = 3 with arr[4] = 3
They are equal, no change
unique_pos = 3

Final result:
Length of unique elements = 3
Unique elements = arr[:3] -> [1, 2, 3]

arr = [1,1,2,2,2,2,3,4,4,4,5,5,6]

def remove_duplicates(arr: list[int | str]):
    n = len(arr)
    unique_pos = 1

    for i in range(1, n):
        if arr[i] != arr[i-1]:
            arr[unique_pos] = arr[i]
            unique_pos += 1
    return unique_pos

unique_pos = remove_duplicates(arr) # 6
print(arr) # [1, 2, 3, 4, 5, 6, 3, 4, 4, 4, 5, 5, 6]

Medium: Rotate Array

• Problem: Given an integer array nums, rotate the array to the right by k steps, where k is non-negative. Perform the rotation in-place.
• Example: Input: nums = [1,2,3,4,5,6,7], k = 3 -> Output: [5,6,7,1,2,3,4]

Steps:
[1,2,3,4,5,6,7], k=3

1. Reverse 0 to k: [1,2,3,4] => [4,3,2,1]
2. Reverse k to n: [5,6,7] => [7,6,5]
3. Reverse entire array: [4,3,2,1,7,6,5] => [5,6,7,1,2,3,4]

Hard: First Missing Positive

• Problem: Given an unsorted integer array nums, return the smallest missing positive integer. You must implement an algorithm that runs in O(N) time and uses O(1) auxiliary space.
• Example: Input: nums = [3,4,-1,1] -> Output: 2

• Approach: Use the array itself as a hash map. Try to place each positive number x at index x-1. Iterate and find the first index i where nums[i] != i+1.

• Approach 1: Use extra space: 0(n) to maintain True, False mark in an array of size n

arr[n+1]
[False, False, True......]
ans: 0 + 1

def get_smallest_missing_positive_number(arr: list[int]) -> int:
    n = len(arr)
    freq_array = [False] * n

    for item in arr:
        if 1 <= item <= n:      # valid range
            freq_array[item-1] = True

    for i in range(n):
        if freq_array[i] == False:
            return i + 1
    return n + 1

• Approach 2: Use the same array to mark element presence

TC: 0(n)
SC: 0(1)

[3, 7, -1, 1]

Step 1: Clean invalid numbers by replacing it with n+1
n = 4
<=0 or >n
[3, 5, 5, 1]

Mark 3 presence in the array:
3-1 = 2 so mark element at index 2 as negative: [3,5,-5,1]

Mark 5 presence in the array:
No need to do as 5 > n

Mark 5 presence in the arry:
No need to do as 5 >n

Mark 1 presence in the array:
1-1 = 0: so make element at 0 as negative: [-3, 5, -5, 1]

Now, find first element which is positive
i=1, we have +ve num so ans: i+1 = 2

def clean_list(num: list[int], n: int) -> list[int]:
    for i in range(0, n):
        if num[i] <= 0 or num[i] > n:
            num[i] = n+1
    return num

def mark_element_presence(num: list[int], n: int) -> list[int]:
    for i in range(n):
        if 1 <= abs(num[i]) <= n:
            target_index = abs(num[i]) - 1
            if num[target_index] > 0:
                num[target_index] *= -1
    return num

def get_smallest_missing_positive(num: list[int]):
    n = len(num)

    # Clean the list
    num = clean_list(num=num, n=n)

    num = mark_element_presence(num=num, n=n)

    for i in range(0, n):
        if num[i] > 0:
            return i+1
    return n+1

Pattern 6: Hashing / Frequency Counting

Easy: Contains Duplicate

• Problem: Given an integer array nums, return true if any value appears at least twice in the array, and return false if every element is distinct.
• Example: Input: nums = [1,2,3,1] -> Output: true
• Approach: Use a hash set to store seen elements. Iterate through the array; if an element is already in the set, return true. Otherwise, add it.

def is_duplicate_exists(arr: list) -> bool:
    freq = {}
    for item in arr:
        freq[item] = freq.get(item, 0) + 1

    for item, count in freq.items():
        if count >= 2:
            return True
    return False

nums = [1,2,3,4]
print(is_duplicate_exists(arr=nums))

Medium: Group Anagrams

• Problem: Given an array of strings strs, group the anagrams together. You can return the answer in any order.
• An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.
• Example: Input: strs = ["eat","tea","tan","ate","nat","bat"] -> Output: [["bat"],["nat","tan"],["ate","eat","tea"]]
• Approach: For each string, create a canonical representation (e.g., sorted string or character count array). Use this representation as a key in a hash map, and store lists of anagrams as values.

def group_anagrams(strs: list[str]) -> list[list[str]]:
    word_keys: dict[str, list] = {}

    for item in strs:
        chars: list = sorted(item)
        key = "".join(chars)

        if key not in word_keys.keys():
            word_keys[key] = [item]
        else:
            word_keys[key].append(item)
    return list(word_keys.values())

strs = ["eat","tea","tan","ate","nat","bat"]
print(group_anagrams(strs=strs))

Hard: Longest Consecutive Elements Sequence

• Problem: Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence.
• You must write an algorithm that runs in O(N) time.
• Example: Input: nums = [100,4,200,1,3,2] -> Output: 4 (The longest consecutive sequence is [1, 2, 3, 4])
• Approach: Store all numbers in a hash set for O(1) lookups. Iterate through the set. For each number, check if number - 1 exists. If not, it's a potential start of a sequence. Then count the consecutive numbers from there by checking number + 1, number + 2, etc.

def get_longest_consecutive(arr: list[int]) -> int:
    num_set = set(arr)
    longest_consecutive = 0
    current_sequence_length = 0

    for num in num_set:
        current_num = num
        current_sequence_length = 1

        while current_num + 1 in num_set:
            current_num += 1
            current_sequence_length += 1

        longest_consecutive = max(longest_consecutive, current_sequence_length)
    return longest_consecutive

nums = [100,4,4,200,201,202,203,204,205,1,2]

Time Complexity: 0(n^2)
We are re-checking for sequence for every single element in the array.

• Optimized approach - run while loop only when sequence is started

nums = [1,2,3,4,5,10,11,16,17,18,19,20,21,22,23]

1 - run the while loop
1-1=0 and 0 in num_Set = No

10 - run the while loop
(10-1) = 9 and 9 in num set = No

16 - run the while loop
(16-1) = 15 and 15 in num set = No

3-1=2 and 2 in num set = Yes


num-1 not in num_set:
    while loop

def get_longest_consecutive(arr: list[int]) -> int:
    num_set = set(arr)
    longest_consecutive = 0
    current_sequence_length = 0

    for num in num_set:
        if num-1 not in num_set:
            current_num = num
            current_sequence_length = 1

            while current_num + 1 in num_set:
                current_num += 1
                current_sequence_length += 1
        longest_consecutive = max(longest_consecutive, current_sequence_length)
    return longest_consecutive

nums = [1,2,3,4,5,10,11,16,17,18,19,20,21,22,23]

Pattern 7: Kadane's Algorithm & Subarray Problems

Easy: Maximum Subarray Sum (Kadane's Algorithm)

• Problem: Given an integer array nums, find the subarray with the largest sum, and return its sum.
• A subarray is a contiguous non-empty sequence of elements within an array.
• Example: Input: nums = [-2,1,-3,4,-1,2,1,-5,4] -> Output: 6 (subarray [4,-1,2,1])

- Find current sum and if current sum becomes less than 0, set the current sum to 0

def maximum_sum_subarray(num: list[int]):
    if not num:
        return -1

    max_sum = num[0]
    current_sum = 0

    for item in num:
        current_sum += item

        max_sum = max(max_sum, current_sum)

        if current_sum <= 0:
            current_sum = 0

    return max_sum

Medium: Maximum Product Subarray

• Problem: Given an integer array nums, find a contiguous non-empty subarray within the array that has the largest product, and return the product.
• Example: Input: nums = [2,3,-2,4] -> Output: 6 (subarray [2,3])

# Maximum Product Subarray Example

**Array:** [2, 3, -2, 4]  

We track three values at each step:  
- `max_here` → max product ending at current index  
- `min_here` → min product ending at current index (to handle negatives)  
- `answer` → overall max product so far  

| Index | Value | max_here | min_here | answer |
|-------|-------|----------|----------|--------|
| 0     | 2     | 2        | 2        | 2      |
| 1     | 3     | 6        | 3        | 6      |
| 2     | -2    | -2       | -12      | 6      |
| 3     | 4     | 4        | -48      | 6      |

**Explanation:**  
- At index 2, -2 flips the sign: max becomes -2, min becomes -12.  
- At each step, `answer` keeps the largest `max_here` seen so far.  

**Final Answer:** 6 (subarray [2,3])

def get_maximum_product_subarray(num: list[int]):
    if not num:
        return -1

    max_product = num[0]
    min_product = num[0]
    answer = num[0]

    for item in num[1:]:
        prev_max = max_product
        prev_min = min_product

        max_product = max(item, item * prev_max, item * prev_min)
        min_product = min(item, item * prev_max, item * prev_min)

        answer = max(answer, max_product)
    return answer

Hard: Maximum Sum Circular Subarray

• Problem: Given a circular integer array nums (the next element of nums[n-1] is nums[0]), return the maximum possible sum of a non-empty subarray.
• Example: Input: nums = [1,-2,3,-2] -> Output: 3 (subarray [3])

# Maximum Sum Circular Subarray – Quick Revision

**Problem:** Find the maximum sum of a non-empty subarray in a circular array `nums` (wraps around).

**Example:**  
`nums = [5, -3, 5]` → max circular sum = 10 (subarray `[5, 5]`), normal max sum = 7 (subarray `[5, -3, 5]`).

**Approach:**  
1. **Normal max subarray (Kadane’s):**  
   - `curr_max = max(num, curr_max + num)` → max sum ending at current element  
   - `max_sum = max(max_sum, curr_max)` → overall max sum  

2. **Circular max subarray:**  
   - `curr_min = min(num, curr_min + num)` → min sum ending at current element  
   - `min_sum = min(min_sum, curr_min)` → overall min sum  
   - `total_sum = sum(nums)`  
   - Circular max sum = `total_sum - min_sum`  

3. **Edge case:** If all numbers are negative, circular sum is invalid → return normal max sum.

**Example Walkthrough (`nums = [5, -3, 5]`):**  
- `total_sum = 7`, `max_sum = 7`, `min_sum = -3` → circular sum = 7 - (-3) = 10 ✅  
- Wrap-around subarray contributing = `[5, 5]` (skips -3).  

**Key Idea:**  
- Normal subarray → Kadane’s  
- Circular subarray → total sum minus minimum subarray sum  
- All negative numbers → pick max element  

**Time Complexity:** O(n), **Space Complexity:** O(1)

def get_maximum_sum_circular_subarray(num: list[int]):
    if not num:
        return -1

    max_sum = curr_max = num[0]
    min_sum = curr_min = num[0]
    total = num[0]

    for item in num[1:]:
        # Max subarray
        curr_max = max(item, curr_max + item)
        max_sum = max(max_sum, curr_max)

        # Min subarray
        curr_min = min(item, curr_min + item)
        min_sum = min(min_sum, curr_min)

        total += item

    # If all numbers are negative
    if max_sum < 0:
        return max_sum

    return max(max_sum, total - min_sum)

Pattern 8: Cyclic Sort

Easy: Find the Missing Number

• Problem: Given an array nums containing n distinct numbers in the range [0, n], return the only number in the range that is missing from the array.
• Example: Input: nums = [3,0,1] -> Output: 2
• Approach: Use Cyclic Sort to place nums[i] at index nums[i]. Then iterate and find the first index i where nums[i] != i.Alternatively, sum up numbers from 0 to n and subtract the sum of elements in the array.

[3, 0, 1] => 2

3:
    correct index for 3 -> skip since 3 > n-1

0:
    correct index for 0 -> at index 0
    swap 3, 0 -> [0, 3, 1]

1:
    correct index for 1 -> at index 1
    from [0, 3, 1] -> swap 3, 1 -> [0, 1, 3]

iterate over [0, 1, 3]
check number at i = i ?
    2 == 3 -> fails -> missing number

def get_missing_number(num: list[int]):
    n = len(num)
    i = 0

    while i < n:
        correct_index = num[i]

        if num[i] < n and num[correct_index] != num[i]:
            num[i], num[correct_index] = num[correct_index], num[i]
        else:
            i += 1

    for index, item in enumerate(num):
        if index != item:
            return index
    return n

Note: - For else part (i += 1): We only move to the next index if the current number is already at the correct position or it is out of range.

Medium: Find All Duplicates in an Array

• Problem: Given an integer array nums of length n where all the integers of nums are in the range [1, n] and each integer appears once or twice, return an array of all the integers that appear twice.
• You must write an algorithm that runs in O(N) time and uses only constant extra space.
• Example: Input: nums = [4,3,2,7,8,2,3,1] -> Output: [2,3]
• Approach: Use Cyclic Sort. Iterate through the array. If nums[i] is not at its correct position (nums[i] != nums[nums[i]-1]), swap it. If it's a duplicate (i.e., nums[i] == nums[nums[i]-1]), move on. After placing elements, iterate again to find numbers not at their correct positions. A clever alternative is to mark visited numbers by negating elements at indices.

[4,3,2,7,8,2,3,1]

4:
    mark 4 as present: [4,3,2,-7,8,2,3,1]
3:
    mark 3 as present: [4,3,-2,-7,8,2,3,1]
2:
    mark 2 as present: [4,-3,-2,-7,8,2,3,1]
7:
    mark 7 as present: [4,-3,-2,-7,8,2,-3,1]
8:
    mark 8 as present: [4,-3,-2,-7,8,2,-3,-1]
2:
    mark 2 as present: [4,-3,-2,-7,8,2,-3,-1]: since -3 is already negative -> so add in duplicate

def get_duplicate_items(num: list[int]) -> list[int]:
    n = len(num)
    duplicates = []
    i = 0

    while i < n:
        number_index = abs(num[i]) - 1

        if num[number_index] < 0:
            duplicates.append(abs(num[i]))
        else:
            num[number_index] *= -1
        i += 1
    return duplicates

Hard: Find the Corrupt Pair (Set Mismatch)

• Problem: You have a set of integers s, which originally contained all the numbers from 1 to n.
• Unfortunately, due to an error, one of the numbers in s got duplicated to another number in the set, which results in repetition of one number and loss of another number.
• Given an integer array nums representing the data status of this set after the error, return the sum of the duplicate number and the missing number.
• Example: Input: nums = [1,2,2,4] -> Output: [2,3] (2 is duplicate, 3 is missing)
• Approach: Use Cyclic Sort to place each number x at index x-1. After the rearrangement, iterate through the array. The index i where nums[i] is not equal to i+1 indicates that nums[i] is the duplicate and i+1 is the missing number.

[1,2,2,4]

1 -> mark 1 as present-> [-1,2,2,4]
2 -> mark 2 as present -> [-1, -2, 2, 4]
2 -> mark 2 as present -> [-1, -2, 2, 4] -> number is already negative, so add it in pair -> [2]
4 -> mark 4 as present -> [-1, -2, 2, -4]

Iterate over final array and find positive number: -> 2 at index 2 -> element is 2+1 = 3 => [2,3]

def get_corrupt_pair(num: list[int]):
    n = len(num)
    corrupt_pair = []

    for i in range(n):
        correct_index = abs(num[i]) - 1
        if num[correct_index] < 0:
            corrupt_pair.append(abs(num[i]))
        else:
            num[correct_index] *= -1

    for i in range(n):
        if num[i] > 0:
            corrupt_pair.append(i + 1)

    return corrupt_pair

Pattern 9: Interval Problems

Easy: Check for Overlapping Intervals

• Problem: Given a collection of intervals, determine if any two intervals overlap.
• Example: Input: intervals = [[1,3],[4,6],[7,9]] -> Output: false; Input: intervals = [[1,3],[2,4]] -> Output: true
• Approach: Sort intervals by their start times. Then, iterate and check if current_end is greater than or equal to next_start.

def is_interval_overlaps(intervals: list[list[int]]) -> bool:
    if not intervals:
        return False

    # Sort intervals by start time
    intervals.sort(key=lambda x: x[0])

    prev_end = intervals[0][1]  # end of first interval

    for current_start, current_end in intervals[1:]:
        if prev_end >= current_start:  # overlap found
            return True
        prev_end = current_end  # update prev_end

    return False

Medium: Insert Interval

• Problem: You are given an array of non-overlapping intervals intervals, sorted by their start times, and a newInterval. Insert newInterval into intervals such that intervals is still sorted in ascending order by start time and remains non-overlapping.

• Example: Input: intervals = [[1,3],[6,9]], newInterval = [2,5] -> Output: [[1,5],[6,9]]

• Approach: Iterate through existing intervals. Add intervals that come before newInterval or after newInterval without overlap. For overlapping intervals, merge them with newInterval.

### Example Walkthrough

**Input**  
intervals = [[1,3],[6,9]]  
newInterval = [2,5]  

---

**Step 1: Add intervals that end before newInterval starts**  
- newInterval starts at 2.  
- [1,3] ends at 3 → not < 2 → stop here.  
- Result = []

---

**Step 2: Merge overlapping intervals**  
- Check [1,3] with [2,5]:  
  - Overlaps since 3 ≥ 2  
  - Merge → [min(1,2), max(3,5)] = [1,5]  
  - newInterval becomes [1,5]  
- Next interval [6,9]:  
  - Starts at 6, which is > newInterval’s end (5) → stop merging  
- Add merged interval → Result = [[1,5]]

---

**Step 3: Add intervals that start after newInterval ends**  
- Add [6,9]  
- Result = [[1,5],[6,9]]

---

**Output**  
[[1,5],[6,9]]

def insert_interval(intervals: list[list[int]], new_interval: list[int]) -> list[list[int]]:
    result = []
    i = 0
    n = len(intervals)

    # Step 1: add all intervals before new_interval
    while i < n and intervals[i][1] < new_interval[0]:
        result.append(intervals[i])
        i += 1

    # Step 2: merge overlaps
    while i < n and intervals[i][0] <= new_interval[1]:
        new_interval[0] = min(new_interval[0], intervals[i][0])
        new_interval[1] = max(new_interval[1], intervals[i][1])
        i += 1
    result.append(new_interval)

    # Step 3: add all intervals after new_interval
    while i < n:
        result.append(intervals[i])
        i += 1

    return result

Hard: Meeting Rooms II

• Problem: Given an array of meeting time intervals intervals where intervals[i] = [start_i, end_i], find the minimum number of conference rooms required.
• Example: Input: intervals = [[0, 30],[5, 10],[15, 20]] -> Output: 2 (One room for [0,30], another for [5,10] and [15,20])

Approach:
- The maximum number of meetings that takes place concurrenty is the number of rooms that are required.
- Have two pointers for start and end time.

[[0, 30], [5, 10], [15, 20]]

Start Times: [0, 5, 15]
End Times: [10, 20, 30]

0 < 10 → add 1 room (room_required = 1)
5 < 10 → add 1 room (room_required = 2)
15 >= 10 → earliest meeting ended, move end pointer to 20, decrease room_required by 1 (room_required = 1)
15 < 20 → add 1 room (room_required = 2)

def get_number_of_meeting_room(intervals: list[list[int]]) -> int:
    if not intervals:
        return 0

    # Separate and sort start and end times
    start_times = sorted([i[0] for i in intervals])
    end_times = sorted([i[1] for i in intervals])

    s, e = 0, 0  # pointers for start and end
    room_required, max_rooms = 0, 0

    while s < len(intervals):
        if start_times[s] < end_times[e]:
            # need a new room
            room_required += 1
            s += 1
        else:
            # one meeting ended, reuse room
            room_required -= 1
            e += 1

        max_rooms = max(max_rooms, room_required)

    return max_rooms