Arrays & Sliding Window (Medium)Master medium-level array problems including Sliding Window, Two Pointers, and Kadane's Algorithm.

121. Maximum Subarray Sum (Kadane's Algorithm)

Problem Statement

Given an integer array `nums`, find the contiguous subarray (containing at least one number) which has the largest sum and return *its sum*. **Example 1:** ``` Input: nums = [-2,1,-3,4,-1,2,1,-5,4] Output: 6 Explanation: [4,-1,2,1] has the largest sum = 6. ``` **Example 2:** ``` Input: nums = [1] Output: 1 ```

Approach

1. **Understand the Goal**: We want to find the maximum sum of a *contiguous* subarray. 2. **Kadane's Algorithm**: * Iterate through the array. * Maintain a `current_sum`. Only add the next element to `current_sum` if `current_sum` is positive. If `current_sum` is negative, it's better to start a new subarray from the current element. * Wait, the logic is: `current_sum = max(num, current_sum + num)`. This decides whether to extend the existing subarray or start a new one. * Keep track of the `max_sum` found so far. 3. **Edge Cases**: Array with all negative numbers (should return the single largest element, which is the least negative one).

Solution

def maxSubArray(nums):
    max_sum = float('-inf')
    current_sum = 0
    
    for num in nums:
        current_sum = current_sum + num
        if current_sum > max_sum:
            max_sum = current_sum
        if current_sum < 0:
            current_sum = 0
            
    return max_sum

122. Longest Subarray with Sum K

Problem Statement

Given an array containing **N** integers and an integer **K**, your task is to find the length of the longest sub-array with the sum of the elements equal to **K**. **Example 1:** ``` Input: nums = [10, 5, 2, 7, 1, 9], k = 15 Output: 4 Explanation: The sub-array is [5, 2, 7, 1]. ``` **Example 2:** ``` Input: nums = [-1, 2, 3], k = 6 Output: 0 ```

Approach

` 1. **Prefix Sum Map**: A common technique for subarray sum problems. 2. **Logic**: * Maintain a running `current_sum`. * Store `current_sum` and its index in a hash map: `{sum: index

Solution

`def lenOfLongSubarr(arr, k):
    sum_map = {

123. Subarray with Given Sum (Positive Numbers)

Problem Statement

Given an unsorted array of **positive** integers, find a continuous subarray which adds to a given number `s`. Return the left and right indexes of the subarray (1-based index). If no such subarray exists, return `[-1]`. **Example 1:** ``` Input: arr = [1, 2, 3, 7, 5], s = 12 Output: [2, 4] Explanation: The sum of elements from 2nd position to 4th position is 12. ```

Approach

1. **Sliding Window**: Since numbers are positive, the sum strictly increases as we add elements. 2. **Logic**: * Use two pointers, `left` and `right`. * Expand `right` adding elements to `current_sum`. * While `current_sum > s`, shrink from `left`. * If `current_sum == s`, we found it. Return `[left+1, right+1]`.

Solution

def subarraySum(arr, s):
    left = 0
    current_sum = 0
    
    for right in range(len(arr)):
        current_sum += arr[right]
        
        while current_sum > s and left < right:
            current_sum -= arr[left]
            left += 1
            
        if current_sum == s:
            return [left + 1, right + 1]
            
    return [-1]

124. Product of Array Except Self

Problem Statement

Given an integer array `nums`, return an array `answer` such that `answer[i]` is equal to the product of all the elements of `nums` except `nums[i]`. The product of any prefix or suffix of `nums` is guaranteed to fit in a 32-bit integer. **You must not use division.** **Example 1:** ``` Input: nums = [1,2,3,4] Output: [24,12,8,6] ```

Approach

1. **Problem**: We can't use division (so can't calculate total product and divide by `nums[i]`). 2. **Approach**: Use prefix and suffix products. * `answer[i]` = (product of all nums to the left) * (product of all nums to the right). 3. **Step 1**: Traverse left to right, storing prefix products in the `answer` array. 4. **Step 2**: Traverse right to left, maintaining a running `suffix_product` and multiplying it with the existing `answer[i]`.

Solution

def productExceptSelf(nums):
    n = len(nums)
    answer = [1] * n
    
    # Left pass
    prefix = 1
    for i in range(n):
        answer[i] = prefix
        prefix *= nums[i]
        
    # Right pass
    suffix = 1
    for i in range(n - 1, -1, -1):
        answer[i] *= suffix
        suffix *= nums[i]
        
    return answer

125. Maximum Product Subarray

Problem Statement

Given an integer array `nums`, find a contiguous non-empty subarray within the array that has the largest product, and return *the product*. **Example 1:** ``` Input: nums = [2,3,-2,4] Output: 6 Explanation: [2,3] has the largest product 6. ``` **Example 2:** ``` Input: nums = [-2,0,-1] Output: 0 ```

Approach

1. **Challenge**: Negative numbers can flip the sign (min becomes max and vice versa). A zero resets the chain. 2. **Approach**: Maintain both `max_so_far` and `min_so_far` at each position. 3. **Iteration**: * If current number is negative, swap `max_so_far` and `min_so_far`. * `max_so_far = max(curr, max_so_far * curr)` * `min_so_far = min(curr, min_so_far * curr)` * Update global result `ans = max(ans, max_so_far)`.

Solution

def maxProduct(nums):
    if not nums: return 0
    
    max_prod = nums[0]
    min_prod = nums[0]
    result = max_prod
    
    for i in range(1, len(nums)):
        curr = nums[i]
        
        # If negative, max and min swap roles
        if curr < 0:
            max_prod, min_prod = min_prod, max_prod
            
        max_prod = max(curr, max_prod * curr)
        min_prod = min(curr, min_prod * curr)
        
        result = max(result, max_prod)
        
    return result

129. Find Missing and Repeating Number

Problem Statement

` Given an unsorted array `arr` of size `n` of non-negative integers. One number 'A' from set {1, 2, ...n

Approach

1. **Math Approach**: Use sum of N numbers and sum of squares. * `val1 = Sum(1..N) - Sum(arr)` -> gives `Missing - Repeating`. * `val2 = SumSq(1..N) - SumSq(arr)` -> gives `Missing^2 - Repeating^2`. * `val2 = (Missing - Repeating)(Missing + Repeating)`. * Solve the system of two equations.

Solution

def findMissingAndRepeating(arr):
    n = len(arr)
    
    # Expected sums
    sum_n = n * (n + 1) // 2
    sum_sq_n = n * (n + 1) * (2 * n + 1) // 6
    
    # Actual sums
    actual_sum = 0
    actual_sum_sq = 0
    for x in arr:
        actual_sum += x
        actual_sum_sq += x * x
        
    # Equations
    # x - y = diff_sum (Missing - Repeating)
    # x^2 - y^2 = diff_sq_sum
    
    # Since x represents Repeating in standard formulas, wait... 
    # Let's say x is missing, y is repeating.
    # Sum(arr) has y twice, no x. Expected has x once, y once.
    # Sum(arr) - Sum(N) = y - x
    
    y_minus_x = actual_sum - sum_n 
    y2_minus_x2 = actual_sum_sq - sum_sq_n
    
    # (y-x)(y+x) = y2_minus_x2
    y_plus_x = y2_minus_x2 // y_minus_x
    
    # 2y = (y-x) + (y+x)
    repeating = (y_minus_x + y_plus_x) // 2
    missing = repeating - y_minus_x
    
    return [repeating, missing]

135. Container With Most Water

Problem Statement

You are given an integer array `height` of length `n`. There are `n` vertical lines drawn such that the two endpoints of the `i`-th line are `(i, 0)` and `(i, height[i])`. Find two lines that together with the x-axis form a container, such that the container contains the most water. Return the maximum amount of water. **Example:** ``` Input: height = [1,8,6,2,5,4,8,3,7] Output: 49 Explanation: The max area is between index 1 (height 8) and index 8 (height 7). Width is 7, min-height is 7, area = 49. ```

Approach

1. **Two Pointers**: Start with pointers at the absolute beginning and end of the array. 2. **Logic**: * Area = `(right - left) * min(height[left], height[right])`. * To possibly increase area, we want to try and find a taller line. * Move the pointer pointing to the *shorter* line inward (because moving the taller one would only decrease width without helping height).

Solution

def maxArea(height):
    left = 0
    right = len(height) - 1
    max_water = 0
    
    while left < right:
        width = right - left
        h = min(height[left], height[right])
        max_water = max(max_water, width * h)
        
        if height[left] < height[right]:
            left += 1
        else:
            right -= 1
            
    return max_water

126. Find the Duplicate Number

Problem Statement

Given an array of integers `nums` containing `n + 1` integers where each integer is in the range `[1, n]` inclusive. There is only **one repeated number** in `nums`, return this repeated number. You must solve the problem **without** modifying the array `nums` and uses only constant extra space. **Example 1:** ```python Input: nums = [1,3,4,2,2] Output: 2 ```

Approach

1. **Constraint**: Cannot modify array (no sort) and O(1) space (no hash set). 2. **Pattern**: Cycle Detection (Floyd's Tortoise and Hare). 3. **Mapping**: Treat values as pointers to indices. Since values are [1, n], they point inside the array. 4. **Logic**: * Slow/Fast pointers to find cycle intersection. * Reset slow to head, move both at same speed to find entrance to cycle. * Cycle entrance = Duplicate number.

Solution

def findDuplicate(nums):
    slow, fast = 0, 0
    while True:
        slow = nums[slow]
        fast = nums[nums[fast]]
        if slow == fast:
            break
            
    slow2 = 0
    while True:
        slow = nums[slow]
        slow2 = nums[slow2]
        if slow == slow2:
            return slow

127. Majority Element

Problem Statement

Given an array `nums` of size `n`, return the majority element. The majority element is the element that appears more than `⌊n / 2⌋` times. You may assume that the majority element always exists in the array. **Example 1:** ```python Input: nums = [2,2,1,1,1,2,2] Output: 2 ```

Approach

1. **Constraint**: O(n) time and O(1) space. 2. **Algorithm**: Boyer-Moore Voting Algorithm. 3. **Logic**: * Maintain a `candidate` and a `count`. * If `count` is 0, set current num as candidate. * If num == candidate, increment count. * Else decrement count. * The remaining candidate is the majority.

Solution

def majorityElement(nums):
    count = 0
    candidate = None
    
    for num in nums:
        if count == 0:
            candidate = num
        count += (1 if num == candidate else -1)
        
    return candidate

128. Merge Intervals

Problem Statement

Given an array of `intervals` where `intervals[i] = [starti, endi]`, merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input. **Example 1:** ```python Input: intervals = [[1,3],[2,6],[8,10],[15,18]] Output: [[1,6],[8,10],[15,18]] Explanation: Since intervals [1,3] and [2,6] overlap, merge them into [1,6]. ```

Approach

1. **Sorting**: Sort intervals by start time. 2. **Iteration**: * Start with the first interval in result list. * For each subsequent interval: * If it overlaps with the last added interval (current.start <= last.end), merge them (last.end = max(last.end, current.end)). * Otherwise, add it as a new interval.

Solution

def merge(intervals):
    if not intervals:
        return []
        
    intervals.sort(key=lambda x: x[0])
    merged = [intervals[0]]
    
    for current in intervals[1:]:
        last = merged[-1]
        
        if current[0] <= last[1]: # Overlap
            last[1] = max(last[1], current[1])
        else:
            merged.append(current)
            
    return merged

130. Rotate Image

Problem Statement

You are given an `n x n` 2D matrix representing an image, rotate the image by 90 degrees (clockwise). You have to rotate the image **in-place**, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation. **Example 1:** ```python Input: matrix = [[1,2,3],[4,5,6],[7,8,9]] Output: [[7,4,1],[8,5,2],[9,6,3]] ```

Approach

1. **Observation**: 90 degree rotate = Transpose + Reverse Rows. 2. **Transpose**: Swap `matrix[i][j]` with `matrix[j][i]` for `i < j`. 3. **Reverse**: Reverse each row.

Solution

def rotate(matrix):
    n = len(matrix)
    
    # Transpose
    for i in range(n):
        for j in range(i, n):
            matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
            
    # Reverse rows
    for i in range(n):
        matrix[i].reverse()

131. Search in Rotated Sorted Array

Problem Statement

There is an integer array `nums` sorted in ascending order (with distinct values). Prior to being passed to your function, `nums` is possibly rotated at an unknown pivot index `k`. Given the array `nums` after the possible rotation and an integer `target`, return the index of `target` if it is in `nums`, or `-1` if it is not in `nums`. You must write an algorithm with `O(log n)` runtime complexity. **Example 1:** ```python Input: nums = [4,5,6,7,0,1,2], target = 0 Output: 4 ```

Approach

1. **Binary Search**: Standard `log n` approach. 2. **Logic**: * Find the middle element. * One half must be sorted. Check if left half `nums[low] <= nums[mid]` is sorted. * If left is sorted: Check if target is in that range `nums[low] <= target < nums[mid]`. If yes, search left, else search right. * If right is sorted: Check if target is in that range `nums[mid] < target <= nums[high]`. If yes, search right, else search left.

Solution

def search(nums, target):
    low, high = 0, len(nums) - 1
    
    while low <= high:
        mid = (low + high) // 2
        if nums[mid] == target:
            return mid
            
        # Left half is sorted
        if nums[low] <= nums[mid]:
            if nums[low] <= target < nums[mid]:
                high = mid - 1
            else:
                low = mid + 1
        # Right half is sorted
        else:
            if nums[mid] < target <= nums[high]:
                low = mid + 1
            else:
                high = mid - 1
                
    return -1

132. Find Peak Element

Problem Statement

A peak element is an element that is strictly greater than its neighbors. Given a 0-indexed integer array `nums`, find a peak element, and return its index. If the array contains multiple peaks, return the index to **any of the peaks**. You may imagine that `nums[-1] = nums[n] = -∞`. In other words, an element is always considered to be strictly greater than a neighbor that is outside the array. You must write an algorithm that runs in `O(log n)` time. **Example 1:** ```python Input: nums = [1,2,3,1] Output: 2 Explanation: 3 is a peak element and your function should return the index number 2. ```

Approach

1. **Binary Search**: Since we need O(log n). 2. **Observation**: If `nums[mid] < nums[mid+1]`, we are on an uphill slope -> peak must be to the right. 3. **Observation**: If `nums[mid] > nums[mid+1]`, we are on a downhill slope -> peak must be at `mid` or to the left. 4. **Logic**: * If `nums[mid] < nums[mid+1]`, `low = mid + 1`. * Else, `high = mid`. * Loop until `low == high`.

Solution

def findPeakElement(nums):
    low, high = 0, len(nums) - 1
    
    while low < high:
        mid = (low + high) // 2
        if nums[mid] < nums[mid + 1]:
            low = mid + 1
        else:
            high = mid
            
    return low

133. Sort Colors

Problem Statement

Given an array `nums` 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. We will use the integers `0`, `1`, and `2` to represent the color red, white, and blue, respectively. You must solve this problem without using the library's sort function. **Example 1:** ```python Input: nums = [2,0,2,1,1,0] Output: [0,0,1,1,2,2] ```

Approach

1. **Dutch National Flag Algorithm**: Three pointers. * `low`: boundary for 0s. * `mid`: current element. * `high`: boundary for 2s. 2. **Logic**: * If `nums[mid] == 0`: switch with `low`, increment `low` and `mid`. * If `nums[mid] == 1`: just increment `mid`. * If `nums[mid] == 2`: switch with `high`, decrement `high` (don't increment mid yet as swapped element needs checking).

Solution

def sortColors(nums):
    low, mid, high = 0, 0, len(nums) - 1
    
    while mid <= high:
        if nums[mid] == 0:
            nums[low], nums[mid] = nums[mid], nums[low]
            low += 1
            mid += 1
        elif nums[mid] == 1:
            mid += 1
        else:
            nums[mid], nums[high] = nums[high], nums[mid]
            high -= 1

134. Trapping Rain Water

Problem Statement

Given `n` non-negative integers representing an elevation map where the width of each bar is `1`, compute how much water it can trap after raining. **Example 1:** ```python Input: height = [0,1,0,2,1,0,1,3,2,1,2,1] Output: 6 Explanation: The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. ```

Approach

1. **Two Pointers**: O(n) time, O(1) space. 2. **Logic**: * Water trapped at `i` is determined by `min(max_left, max_right) - height[i]`. * Use pointers `left` and `right`. * Maintain `left_max` and `right_max`. * If `left_max < right_max`, we process left side (limiting factor is left), add `left_max - height[left]` to res, move left. * Else process right side, add `right_max - height[right]` to res, move right.

Solution

def trap(height):
    if not height: return 0
    
    left, right = 0, len(height) - 1
    left_max, right_max = height[left], height[right]
    res = 0
    
    while left < right:
        if left_max < right_max:
            left += 1
            left_max = max(left_max, height[left])
            res += left_max - height[left]
        else:
            right -= 1
            right_max = max(right_max, height[right])
            res += right_max - height[right]
            
    return res

136. Kth Largest Element in an Array

Problem Statement

Given an integer array `nums` and an integer `k`, return the `k`-th largest element in the array. Note that it is the `k`-th largest element in the sorted order, not the `k`-th distinct element. You must solve it in `O(n)` time complexity. **Example 1:** ```python Input: nums = [3,2,1,5,6,4], k = 2 Output: 5 ```

Approach

1. **Solution**: QuickSelect (Hoare's selection algorithm). 2. **Logic**: * This is related to QuickSort. * Pick a pivot. * Partition array such that elements > pivot are on left, < pivot on right (if sorting descending) or vice versa. * Check pivot index position. * If pivot index == k-1, we found it. * If index < k-1, recurse right. * If index > k-1, recurse left.

Solution

import random

def findKthLargest(nums, k):
    target_idx = len(nums) - k
    
    def quick_select(l, r):
        pivot = nums[r]
        p = l
        for i in range(l, r):
            if nums[i] <= pivot:
                nums[p], nums[i] = nums[i], nums[p]
                p += 1
        nums[p], nums[r] = nums[r], nums[p]
        
        if p > target_idx:
            return quick_select(l, p - 1)
        elif p < target_idx:
            return quick_select(p + 1, r)
        else:
            return nums[p]
            
    return quick_select(0, len(nums) - 1)

139. Best Time to Buy and Sell Stock

Problem Statement

You are given an array `prices` where `prices[i]` is the price of a given stock on the `i`-th day. You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock. Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return `0`. **Example 1:** ```python Input: prices = [7,1,5,3,6,4] Output: 5 Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5. ```

Approach

1. **Single Pass**: We need to find the largest difference `prices[j] - prices[i]` where `j > i`. 2. **Logic**: * Iterate through prices. * Keep track of `min_price` found so far. * At each step, calculate `profit = current_price - min_price`. * Update `max_profit`. * Update `min_price` if current is lower.

Solution

def maxProfit(prices):
    min_price = float('inf')
    max_profit = 0
    
    for price in prices:
        if price < min_price:
            min_price = price
        elif price - min_price > max_profit:
            max_profit = price - min_price
            
    return max_profit

142. Maximum Sum Circular Subarray

Problem Statement

Given a circular integer array `nums` of length `n`, return the maximum possible sum of a non-empty subarray of `nums`. A circular array means the end of the array connects to the beginning of the array. **Example 1:** ```python Input: nums = [1,-2,3,-2] Output: 3 Explanation: Subarray [3] has maximum sum 3. ```

Approach

1. **Case 1**: Max subarray is not circular. (Standard Kadane's algorithm). 2. **Case 2**: Max subarray is circular (wraps around). * This means the subarray *excludes* a minimum sum subarray in the middle. * Sum(Max Circular) = Total Sum - Sum(Min Subarray). 3. **Edge Case**: If all numbers are negative, TotalSum - MinSubarray = 0 (empty), which is invalid for "non-empty". In this case, just return standard Kadane's (which picks the max single element).

Solution

def maxSubarraySumCircular(nums):
    total = 0
    max_sum = nums[0]
    cur_max = 0
    min_sum = nums[0]
    cur_min = 0
    
    for num in nums:
        cur_max = max(cur_max + num, num)
        max_sum = max(max_sum, cur_max)
        
        cur_min = min(cur_min + num, num)
        min_sum = min(min_sum, cur_min)
        
        total += num
        
    if max_sum < 0:
        return max_sum
        
    return max(max_sum, total - min_sum)

143. Longest Consecutive Sequence

Problem Statement

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 1:** ```python Input: nums = [100,4,200,1,3,2] Output: 4 Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4. ```

Approach

1. **Set**: Use a hash set for O(1) lookups. 2. **Logic**: * Iterate through each number `num` in the set. * Check if it's the *start* of a sequence (i.e., `num - 1` is NOT in set). * If it is start, count length by checking `num + 1`, `num + 2`, etc. * Update max length. * If not start, skip (it will be counted when we reach the start).

Solution

def longestConsecutive(nums):
    num_set = set(nums)
    longest = 0
    
    for n in num_set:
        # Check if its the start of a sequence
        if (n - 1) not in num_set:
            length = 0
            while (n + length) in num_set:
                length += 1
            longest = max(length, longest)
            
    return longest

Back

Arrays & Sliding Window (Medium) / 121. Maximum Subarray Sum (Kadane's Algorithm)

00:00

1/19

121. Maximum Subarray Sum (Kadane's Algorithm)

Medium

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Example 1:

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

Example 2:

Input: nums = [1]
Output: 1

1
Understand the Goal: We want to find the maximum sum of a contiguous subarray.
2
Kadane's Algorithm:
3
Iterate through the array.
4
Maintain a current_sum. Only add the next element to current_sum if current_sum is positive. If current_sum is negative, it's better to start a new subarray from the current element.
5
Wait, the logic is: current_sum = max(num, current_sum + num). This decides whether to extend the existing subarray or start a new one.
6
Keep track of the max_sum found so far.
7
Edge Cases: Array with all negative numbers (should return the single largest element, which is the least negative one).

PYTHON PLAYGROUND

⏳ Loading editor…