Arrays, Two Pointers, Stacks & Sliding Window

Core techniques that appear in 60%+ of coding interviews

---

Arrays Fundamentals

5 Key Operations You Must Know

Operation	Time Complexity	Notes
Access by index	O(1)	arr[i] - constant time
Insert at end	O(1) amortized	append() - usually constant
Insert at index	O(n)	Shifts all elements after
Delete at index	O(n)	Shifts all elements after
Search (unsorted)	O(n)	Linear scan required

Critical Array Patterns

Python

# 1. In-place reversal
def reverse(arr):
    left, right = 0, len(arr) - 1
    while left < right:
        arr[left], arr[right] = arr[right], arr[left]
        left += 1
        right -= 1

# 2. Prefix sum (for range queries)
prefix = [0]
for num in arr:
    prefix.append(prefix[-1] + num)
# Sum from i to j = prefix[j+1] - prefix[i]

# 3. Dutch National Flag (3-way partition)
def partition(arr, pivot):
    low, mid, high = 0, 0, len(arr) - 1
    while mid <= high:
        if arr[mid] < pivot:
            arr[low], arr[mid] = arr[mid], arr[low]
            low += 1
            mid += 1
        elif arr[mid] > pivot:
            arr[mid], arr[high] = arr[high], arr[mid]
            high -= 1
        else:
            mid += 1

Java

// 1. In-place reversal
void reverse(int[] arr) {
    int left = 0, right = arr.length - 1;
    while (left < right) {
        int tmp = arr[left]; arr[left] = arr[right]; arr[right] = tmp;
        left++; right--;
    }
}

// 2. Prefix sum (for range queries)
int[] buildPrefix(int[] arr) {
    int[] prefix = new int[arr.length + 1];
    for (int i = 0; i < arr.length; i++) prefix[i + 1] = prefix[i] + arr[i];
    return prefix;
    // Sum from i to j = prefix[j+1] - prefix[i]
}

// 3. Dutch National Flag (3-way partition)
void partition(int[] arr, int pivot) {
    int low = 0, mid = 0, high = arr.length - 1;
    while (mid <= high) {
        if (arr[mid] < pivot) {
            int tmp = arr[low]; arr[low] = arr[mid]; arr[mid] = tmp;
            low++; mid++;
        } else if (arr[mid] > pivot) {
            int tmp = arr[mid]; arr[mid] = arr[high]; arr[high] = tmp;
            high--;
        } else { mid++; }
    }
}

Complexity: Time O(n) · Space O(1)

• Time: Single pass through the array with three pointers
• Space: In-place partitioning using only pointer variables

---

Two Pointer Pattern

Transforms O(n^2) brute force into O(n) solutions

When to Use

Signal	Example Problem
Sorted array + pair/triplet search	Two Sum II, 3Sum
Palindrome checking	Valid Palindrome
In-place modification	Remove Duplicates
Merge two sorted arrays	Merge Sorted Array
Container problems	Container With Most Water

WARNING: Two pointers on unsorted arrays is a common interview mistake. Either sort first or use a hash map.

Template: Opposite Direction

Python

def two_pointer_opposite(arr, target):
    """Use when searching for pairs in SORTED array"""
    left, right = 0, len(arr) - 1

    while left < right:
        current_sum = arr[left] + arr[right]

        if current_sum == target:
            return [left, right]  # Found!
        elif current_sum < target:
            left += 1   # Need larger sum
        else:
            right -= 1  # Need smaller sum

    return []  # Not found

Java

int[] twoPointerOpposite(int[] arr, int target) {
    int left = 0, right = arr.length - 1;
    while (left < right) {
        int sum = arr[left] + arr[right];
        if (sum == target) return new int[]{left, right};
        else if (sum < target) left++;
        else right--;
    }
    return new int[]{};
}

Complexity: Time O(n) · Space O(1)

• Time: Each element visited at most once as pointers converge
• Space: Only two pointer variables used

Template: Same Direction (Fast/Slow)

Python

def two_pointer_same_direction(arr):
    """Use for in-place modifications or cycle detection"""
    slow = 0  # Write pointer

    for fast in range(len(arr)):  # Read pointer
        if arr[fast] != val_to_remove:
            arr[slow] = arr[fast]
            slow += 1

    return slow  # New length

Java

int twoPointerSameDirection(int[] arr, int valToRemove) {
    int slow = 0;
    for (int fast = 0; fast < arr.length; fast++) {
        if (arr[fast] != valToRemove) arr[slow++] = arr[fast];
    }
    return slow;
}

Complexity: Time O(n) · Space O(1)

• Time: Single pass through array with fast pointer
• Space: In-place modification using two pointer indices

Classic Problems

Problem	Key Insight	One-Liner Logic
Two Sum II	Sorted + target	Move pointers based on sum comparison
3Sum	Fix one, two-pointer rest	Sort first, skip duplicates
Container With Most Water	Max area	Move the shorter height pointer
Remove Duplicates	Slow/fast pointers	Slow writes only unique values
Valid Palindrome	Compare ends	Skip non-alphanumeric, compare

---

Sliding Window Pattern

Reduces O(n^2) or O(n^3) to O(n) for subarray/substring problems

Fixed vs Variable Window

Decision Guide:

• Fixed Window: "Find max/min sum of k consecutive elements"
• Variable Window: "Find smallest/longest subarray with condition X"

Template: Fixed Window

Python

def fixed_sliding_window(arr, k):
    """Window of exactly k elements"""
    window_sum = sum(arr[:k])
    max_sum = window_sum

    for i in range(k, len(arr)):
        window_sum += arr[i] - arr[i - k]
        max_sum = max(max_sum, window_sum)

    return max_sum

Java

int fixedSlidingWindow(int[] arr, int k) {
    int windowSum = 0;
    for (int i = 0; i < k; i++) windowSum += arr[i];
    int maxSum = windowSum;
    for (int i = k; i < arr.length; i++) {
        windowSum += arr[i] - arr[i - k];
        maxSum = Math.max(maxSum, windowSum);
    }
    return maxSum;
}

Complexity: Time O(n) · Space O(1)

• Time: Single pass after initial window setup
• Space: Only tracking sum and max variables

Template: Variable Window

Python

def variable_sliding_window(arr, target):
    """Expand right, shrink left when condition violated"""
    left = 0
    window_sum = 0
    min_length = float('inf')

    for right in range(len(arr)):
        window_sum += arr[right]

        while window_sum >= target:
            min_length = min(min_length, right - left + 1)
            window_sum -= arr[left]
            left += 1

    return min_length if min_length != float('inf') else 0

Java

int variableSlidingWindow(int[] arr, int target) {
    int left = 0, windowSum = 0, minLength = Integer.MAX_VALUE;
    for (int right = 0; right < arr.length; right++) {
        windowSum += arr[right];
        while (windowSum >= target) {
            minLength = Math.min(minLength, right - left + 1);
            windowSum -= arr[left++];
        }
    }
    return minLength == Integer.MAX_VALUE ? 0 : minLength;
}

Complexity: Time O(n) · Space O(1)

• Time: Each element added and removed from window at most once
• Space: Only tracking window boundaries and sum

Template: Sliding Window with HashMap

Python

def sliding_window_hashmap(s, k):
    """For substring problems with character frequency"""
    from collections import defaultdict

    char_count = defaultdict(int)
    left = 0
    max_length = 0

    for right in range(len(s)):
        char_count[s[right]] += 1

        while len(char_count) > k:
            char_count[s[left]] -= 1
            if char_count[s[left]] == 0:
                del char_count[s[left]]
            left += 1

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

    return max_length

Java

int slidingWindowHashmap(String s, int k) {
    Map<Character, Integer> charCount = new HashMap<>();
    int left = 0, maxLength = 0;
    for (int right = 0; right < s.length(); right++) {
        charCount.merge(s.charAt(right), 1, Integer::sum);
        while (charCount.size() > k) {
            char lc = s.charAt(left);
            charCount.merge(lc, -1, Integer::sum);
            if (charCount.get(lc) == 0) charCount.remove(lc);
            left++;
        }
        maxLength = Math.max(maxLength, right - left + 1);
    }
    return maxLength;
}

Complexity: Time O(n) · Space O(k)

• Time: Each character added and removed from window at most once
• Space: HashMap stores at most k distinct characters

Classic Problems

Problem	Window Type	Key Insight
Max Sum Subarray of Size K	Fixed	Slide and track max
Minimum Size Subarray Sum	Variable	Shrink when sum >= target
Longest Substring Without Repeating	Variable	HashSet to track chars
Longest Substring with K Distinct	Variable	HashMap + count
Minimum Window Substring	Variable	HashMap + "have" vs "need"

---

Stack Essentials

LIFO structure - perfect for matching pairs and "next greater" problems

When Stack is the Answer

Pattern	Signal Words	Example
Matching pairs	"valid", "balanced", "matching"	Valid Parentheses
Next greater/smaller	"next", "previous", "greater", "smaller"	Next Greater Element
Expression evaluation	"calculate", "evaluate", "RPN"	Basic Calculator
Backtracking state	"undo", "history", "path"	Simplify Path
Monotonic sequence	"increasing/decreasing order"	Daily Temperatures

Template: Matching Pairs

Python

def is_valid_parentheses(s):
    """Classic bracket matching"""
    stack = []
    mapping = {')': '(', '}': '{', ']': '['}

    for char in s:
        if char in mapping:  # Closing bracket
            if not stack or stack[-1] != mapping[char]:
                return False
            stack.pop()
        else:  # Opening bracket
            stack.append(char)

    return len(stack) == 0

Java

boolean isValidParentheses(String s) {
    Deque<Character> stack = new ArrayDeque<>();
    for (char c : s.toCharArray()) {
        if (c == '(' || c == '{' || c == '[') stack.push(c);
        else {
            if (stack.isEmpty()) return false;
            char top = stack.pop();
            if ((c == ')' && top != '(') || (c == '}' && top != '{')
                    || (c == ']' && top != '[')) return false;
        }
    }
    return stack.isEmpty();
}

Complexity: Time O(n) · Space O(n)

• Time: Single pass through the string
• Space: Stack stores at most n/2 opening brackets

Template: Monotonic Stack (Decreasing)

Python

def next_greater_element(arr):
    """Find next greater element for each position"""
    n = len(arr)
    result = [-1] * n
    stack = []  # Stores indices

    for i in range(n):
        while stack and arr[stack[-1]] < arr[i]:
            idx = stack.pop()
            result[idx] = arr[i]
        stack.append(i)

    return result

Java

int[] nextGreaterElement(int[] arr) {
    int[] result = new int[arr.length]; Arrays.fill(result, -1);
    Deque<Integer> stack = new ArrayDeque<>();
    for (int i = 0; i < arr.length; i++) {
        while (!stack.isEmpty() && arr[stack.peek()] < arr[i])
            result[stack.pop()] = arr[i];
        stack.push(i);
    }
    return result;
}

Complexity: Time O(n) · Space O(n)

• Time: Each element pushed and popped at most once
• Space: Stack and result array each store up to n elements

Template: Monotonic Stack (Increasing)

Python

def daily_temperatures(temperatures):
    """Days until warmer temperature"""
    n = len(temperatures)
    result = [0] * n
    stack = []  # Stores indices of decreasing temps

    for i in range(n):
        while stack and temperatures[i] > temperatures[stack[-1]]:
            prev_idx = stack.pop()
            result[prev_idx] = i - prev_idx
        stack.append(i)

    return result

Java

int[] dailyTemperatures(int[] temperatures) {
    int[] result = new int[temperatures.length];
    Deque<Integer> stack = new ArrayDeque<>();
    for (int i = 0; i < temperatures.length; i++) {
        while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
            int idx = stack.pop(); result[idx] = i - idx;
        }
        stack.push(i);
    }
    return result;
}

Complexity: Time O(n) · Space O(n)

• Time: Each index pushed and popped at most once
• Space: Stack stores indices; result array stores n elements

Classic Problems

Problem	Stack Type	Key Insight
Valid Parentheses	Regular	Push open, pop on close
Daily Temperatures	Monotonic decreasing	Pop when temp rises
Largest Rectangle in Histogram	Monotonic increasing	Pop when height decreases
Trapping Rain Water	Monotonic or two-pointer	Stack tracks "pits"
Evaluate RPN	Regular	Pop operands, push result

---

Quick Problem Matrix

Problem	Pattern	Key Insight
Two Sum II	Two Pointers	Sorted array, move based on sum
3Sum	Two Pointers	Fix one, two-pointer for rest
Container With Most Water	Two Pointers	Move shorter height pointer
Remove Duplicates from Sorted Array	Two Pointers	Slow/fast pointer in-place
Maximum Subarray Sum (size k)	Fixed Window	Slide, add right, remove left
Minimum Size Subarray Sum	Variable Window	Expand right, shrink left
Longest Substring Without Repeating	Variable Window + HashSet	Shrink on duplicate
Valid Parentheses	Stack	Push open, match on close
Daily Temperatures	Monotonic Stack	Pop when find warmer day
Largest Rectangle in Histogram	Monotonic Stack	Pop on smaller height

---

Interview Applications

How These Patterns Appear in Interviews

1. Two Pointers in Interviews

   • Often combined with binary search for optimization
   • "Find pairs/triplets with specific sum" is a classic Google phone screen question
   • Watch for: sorted array inputs signal two-pointer approach

2. Sliding Window in Interviews

   • Google loves substring problems with character frequency conditions
   • Real-world connection: network packet analysis, log processing
   • Common variation: "Find minimum window containing all characters from target"

3. Stack in Interviews

   • Expression parsing (think Google Sheets formulas)
   • Nested structure validation (HTML/XML parsing)
   • Histogram problems are Google favorites (Largest Rectangle)

Google-Style Problem Combinations

Combination	Example
Two Pointers + Binary Search	"Find pair with sum closest to target"
Sliding Window + HashMap	"Longest substring with at most K distinct characters"
Stack + Arrays	"Trapping Rain Water" (can solve with stack or two pointers)
Monotonic Stack + DP	"Sum of Subarray Minimums"

Interview Tips from Top Sources

1. Start with brute force - Explain why O(n^2) or O(n^3) is inefficient
2. Identify the pattern signal - Sorted array? Use two pointers. Subarray/substring? Try sliding window. Matching or ordering? Consider stack.
3. Handle edge cases explicitly:
   • Empty array
   • Single element
   • All same elements
   • Window size larger than array

---

Quick Reference Card

PATTERN SELECTION FLOWCHART:

Is input sorted or needs pairs/triplets?
    YES -> Two Pointers (opposite direction)

Need to modify array in-place?
    YES -> Two Pointers (same direction)

Looking for contiguous subarray/substring with constraint?
    YES -> Sliding Window
    - Known size k? -> Fixed Window
    - Find min/max length? -> Variable Window

Need matching pairs or "next greater/smaller"?
    YES -> Stack (possibly monotonic)

Need to evaluate expressions or track history?
    YES -> Stack

---

Sources

• Two Pointers Technique - GeeksforGeeks
• LeetCode Two Pointers Problem List
• Master in Two Pointer - LeetCode Discussion
• The Complete Two Pointers Guide
• Top Sliding Window Problems for Interviews - GeeksforGeeks
• LeetCode Sliding Window Problem List
• 10 Sliding Window Patterns for Coding Interviews - LeetCode
• Variable Length Sliding Window - Hello Interview
• Sliding Window Interview Questions & Tips