Arrays & Strings II

Why this module exists

You know the basics: iteration, slicing, hash maps. Now it's time to master the patterns that unlock most array and string problems. This module covers six techniques that appear constantly in interviews:

1. Set membership — O(1) duplicate detection
2. Two pointers — in-place transformations
3. Sliding window — substring/subarray optimization
4. Stacks — matching brackets, monotonic sequences
5. Binary search — finding positions in sorted data
6. Interval merging — combining overlapping ranges

Master these, and you'll recognize solutions faster than you can type them.

---

1) Set Membership: Detecting Duplicates

The brute force way to find duplicates is O(n²) — for each element, scan all others. With a hash set, it's O(n):

func containsDuplicate(nums []int) bool {
    seen := make(map[int]bool)
    for _, n := range nums {
        if seen[n] {
            return true
        }
        seen[n] = true
    }
    return false
}

Pattern: Build a set as you scan. Check membership before inserting.

Variations:

• Find the duplicate value
• Count occurrences of each
• Check if two arrays share any element

---

2) Two Pointers: In-Place Transformation

When you need to modify an array in-place, use a read pointer and a write pointer:

func moveZeroes(nums []int) {
    write := 0
    for read := 0; read < len(nums); read++ {
        if nums[read] != 0 {
            nums[write] = nums[read]
            write++
        }
    }
    // Fill remaining positions with zeroes
    for ; write < len(nums); write++ {
        nums[write] = 0
    }
}

Pattern: Read pointer scans everything. Write pointer marks where to place valid elements.

Variations:

• Remove duplicates from sorted array
• Remove specific value
• Partition array (Dutch flag)

---

3) Sliding Window: Substring Optimization

For problems asking "find the best substring with property X":

func lengthOfLongestSubstring(s string) int {
    lastSeen := make(map[byte]int)
    maxLen := 0
    left := 0

    for right := 0; right < len(s); right++ {
        c := s[right]
        // If character was seen and is within current window
        if idx, ok := lastSeen[c]; ok && idx >= left {
            left = idx + 1  // Shrink window past the duplicate
        }
        lastSeen[c] = right
        if right-left+1 > maxLen {
            maxLen = right - left + 1
        }
    }

    return maxLen
}

Pattern:

1. Expand right to grow the window
2. Shrink left when the window becomes invalid
3. Track the best valid window seen

Variations:

• Minimum window containing all characters
• Maximum sum subarray of size k
• Longest subarray with sum ≤ k

---

4) Stack: Bracket Matching and Monotonic Sequences

Stacks are perfect for matching pairs and tracking "waiting" elements.

Bracket Matching

func isValid(s string) bool {
    stack := []byte{}
    pairs := map[byte]byte{')': '(', ']': '[', '}': '{'}

    for i := 0; i < len(s); i++ {
        c := s[i]
        if c == '(' || c == '[' || c == '{' {
            stack = append(stack, c)
        } else {
            if len(stack) == 0 || stack[len(stack)-1] != pairs[c] {
                return false
            }
            stack = stack[:len(stack)-1]
        }
    }

    return len(stack) == 0
}

Monotonic Stack: Next Greater Element

A monotonic stack keeps elements in sorted order. When a new element breaks the order, you've found the "next greater" for popped elements:

func dailyTemperatures(temperatures []int) []int {
    n := len(temperatures)
    result := make([]int, n)
    stack := []int{} // stack of indices

    for i := 0; i < n; i++ {
        // Pop while current temp is greater than stack top
        for len(stack) > 0 && temperatures[i] > temperatures[stack[len(stack)-1]] {
            j := stack[len(stack)-1]
            stack = stack[:len(stack)-1]
            result[j] = i - j  // Days until warmer
        }
        stack = append(stack, i)
    }

    return result
}

Pattern: Maintain a stack of indices. When new element breaks monotonicity, process popped elements.

---

5) Binary Search: Finding Positions

Binary search isn't just for "find X in sorted array." It's for any problem where you can partition the search space.

Search Insert Position

func searchInsert(nums []int, target int) int {
    lo, hi := 0, len(nums)

    for lo < hi {
        mid := lo + (hi-lo)/2
        if nums[mid] < target {
            lo = mid + 1
        } else {
            hi = mid
        }
    }

    return lo  // First position >= target
}

Key insight: After the loop, lo is the leftmost position where target could be inserted to maintain sorted order.

Variations:

• First occurrence of target
• Last occurrence of target
• First element greater than target
• Search in rotated sorted array

Binary Search Template

// Find first position where condition is true
func binarySearch(n int, condition func(int) bool) int {
    lo, hi := 0, n
    for lo < hi {
        mid := lo + (hi-lo)/2
        if condition(mid) {
            hi = mid
        } else {
            lo = mid + 1
        }
    }
    return lo
}

---

6) Interval Merging

Overlapping intervals can be merged after sorting by start time:

func merge(intervals [][]int) [][]int {
    if len(intervals) == 0 {
        return nil
    }

    // Sort by start time
    sort.Slice(intervals, func(i, j int) bool {
        return intervals[i][0] < intervals[j][0]
    })

    result := [][]int{intervals[0]}

    for i := 1; i < len(intervals); i++ {
        last := result[len(result)-1]
        curr := intervals[i]

        if curr[0] <= last[1] {  // Overlap
            // Extend the last interval
            if curr[1] > last[1] {
                last[1] = curr[1]
            }
        } else {
            result = append(result, curr)
        }
    }

    return result
}

Pattern:

1. Sort intervals by start
2. Compare current interval with the last merged one
3. If overlap (curr.start <= last.end), extend
4. Otherwise, add as new interval

Overlap condition: Two intervals [a,b] and [c,d] overlap if c <= b (when sorted by start).

---

7) Common Mistakes

• Off-by-one in sliding window: Is the window [left, right] or [left, right)?
• Empty stack pop: Always check len(stack) > 0 before popping
• Binary search infinite loop: Use lo + (hi-lo)/2 to avoid overflow, ensure loop terminates
• Interval edge case: [1,5] and [5,10] overlap if you use <=
• Modifying during iteration: Be careful when removing elements while iterating

---

8) Complexity Cheat Sheet

Pattern	Time	Space
Set membership	O(n)	O(n)
Two pointers (in-place)	O(n)	O(1)
Sliding window	O(n)	O(k) for window state
Stack matching	O(n)	O(n)
Monotonic stack	O(n)	O(n)
Binary search	O(log n)	O(1)
Interval merge	O(n log n)	O(n)

---

Outcomes

After this module, you should be able to:

• Use hash sets for O(n) duplicate detection
• Apply two-pointer technique for in-place array modifications
• Implement sliding window for optimal substring problems
• Use stacks for bracket matching and next-greater-element problems
• Write correct binary search for various "find position" problems
• Merge overlapping intervals efficiently

---

7) Monotonic Deque: Sliding Window Maximum

When you need the max in each window, a deque keeps candidates in decreasing order.

Core idea:

1. Drop indices that leave the window.
2. Drop indices whose values are smaller than the current value.
3. The front is always the max.

This yields O(n) time and O(k) space.

---

Practice Set

1. Contains Duplicate (Easy) — Set membership
2. Move Zeroes (Easy) — Two pointers
3. Search Insert Position (Easy) — Binary search
4. Longest Substring Without Repeating Characters (Medium) — Sliding window
5. Valid Parentheses (Easy) — Stack
6. Daily Temperatures (Medium) — Monotonic stack
7. Merge Intervals (Medium) — Sort and sweep
8. Sliding Window Maximum (Medium) — Monotonic deque

Work through them in order. Each builds on concepts from the previous ones.