Array

Two Sum

Use hashmap: value -> index

For each x at index i:

1. Compute need = target - x

2. If need in hashmap, return [hashmap[need], i]

3. Store x: i

   Keeps lookup in O(1)

Best Time to Buy and Sell Stock

Track minimum price so far:

1. Update min_price

2. Compute price - min_price

3. Keep max profit

   One pass, O(n)

Product of Array Except Self

No division:

1. Build prefix products

2. Build suffix products

3. Answer at i = prefix[i] * suffix[i]

   Or do prefix in result array, then multiply by running suffix

   O(n) time, O(1) extra space excluding output

Maximum Subarray

Kadane’s algorithm:

1. curr = max(num, curr + num)

2. best = max(best, curr)

   At each index, either start fresh or extend previous

   O(n)

Contains Duplicate

Use a set:

1. If number already in set, return True

2. Else add it

   O(n) average

Maximum Product Subarray

Track both max and min product ending at current index:

1. Negative number can flip min to max

2. Update curMax, curMin

3. Track global max

   Need both because of negatives

   O(n)

Search in Rotated Sorted Array

Modified binary search:

1. Check mid

2. One half is always sorted

3. Decide whether target lies in sorted half

4. Move left/right accordingly

   O(log n)

3Sum

Sort first:

1. Fix index i

2. Use two pointers l, r for remaining part

3. Move based on sum

4. Skip duplicates for i, l, r

   O(n^2)

Container With Most Water

Two pointers at both ends:

1. Area = min(height[l], height[r]) * (r-l)

2. Move shorter line inward

   Only shorter side can possibly improve area

   O(n)

Sliding Window Maximum

Use monotonic decreasing deque of indices:

1. Remove indices out of window

2. Pop smaller values from back

3. Push current index

4. Front is max of current window

   O(n)

Longest Substring Without Repeating Characters

1. Expand right pointer

2. While duplicate exists, shrink left

3. Track max window size

   O(n)

Minimum Size Subarray Sum

Sliding window for positive numbers:

1. Expand right and add to sum

2. While sum >= target, update answer and shrink left

   Because all numbers are positive, shrinking is valid

   O(n)

Minimum Window Substring

Sliding window + frequency counts:

1. Count chars needed from t

2. Expand right, reduce needed counts

3. When all requirements met, shrink left to minimum valid window

4. Track best window

   Classic variable-size sliding window

Sort Colors

Dutch National Flag:

1. left for 0s, right for 2s, i scans

2. If 0: swap with left, move both

3. If 2: swap with right, move right

4. If 1: just move i

   O(n), in-place

Palindromic Substrings

1. Each index is center for odd palindrome

2. Each gap is center for even palindrome

3. Expand while chars match

4. Count every valid expansion

   O(n^2)

Merge Sorted Array

Fill from the back:

1. Pointer i at end of nums1 valid part

2. Pointer j at end of nums2

3. Pointer k at end of nums1 total size

4. Put larger of nums1[i] and nums2[j] at k

   Avoids shifting elements

Daily Temperatures

Monotonic decreasing stack of indices:

1. For each day, while current temp > stack top temp

2. Pop index and set answer as difference in indices

3. Push current index

   Next greater element pattern

Merge Intervals

Sort by start:

1. Start with first interval

2. If current overlaps last merged, extend end

3. Else append as new interval

   O(n log n) because of sorting

Non-overlapping Intervals

Greedy by end time:

1. Sort by interval end

2. Keep interval with smallest end

3. If next interval overlaps, remove it

4. Else keep it

   Equivalent to maximizing number kept

First Missing Positive (H)

Place each number x in index x-1:

1. While 1 <= x <= n and not already in correct place, swap

2. After placement, first index i where nums[i] != i+1 gives answer i+1

3. If all correct, answer is n+1

   O(n), in-place

Longest Consecutive Sequence

Use set:

1. For each number, only start counting if num-1 not in set

2. Extend forward while num+1 exists

3. Track longest length

   Each sequence counted once

   O(n) average

Jump Game

Greedy from right:

1. Start goal at last index

2. Move leftward

3. If i + nums[i] >= goal, update goal = i

4. At end, can reach if goal == 0

   Work backwards to see if each index can reach goal

Subarray Sum Equals K

Prefix sum + hashmap of frequencies:

1. Maintain running sum s

2. Need previous prefix s-k

3. Add count of s-k to answer

4. Store frequency of s

   Initialize hashmap with {0:1}

   Handles negatives too

Maximum Number of Vowels

Fixed-size sliding window:

1. Count vowels in first window of size k

2. Slide window: add new char, remove old char

3. Track max count

   O(n)