Array Operations and Techniques

Imagine a row of numbered lockers in a school hallway—each locker has a number (starting from 0), they're all the same size, and they're right next to each other. That's exactly what an array is in programming! An array is a contiguous block of memory that stores elements of the same data type in a fixed sequence. Think of it as the most basic container in programming—just like how atoms are building blocks for molecules, arrays are the building blocks for more complex data structures like ArrayLists, stacks, queues, and heaps. Mastering arrays is essential because they appear in over 60% of technical interview questions, and once you understand arrays, every other data structure becomes easier to learn.

Why Arrays Matter in Interviews

Arrays are the most commonly tested data structure in coding interviews. Over 60% of LeetCode problems involve arrays in some form. Mastering array manipulation patterns like two pointers, sliding window, and prefix sums will help you solve a wide variety of problems efficiently.

Array Time Complexity Overview

Understanding the time complexity of array operations is crucial for writing efficient code and analyzing algorithms during interviews.

Java provides several ways to declare and initialize arrays. Understanding these methods is fundamental to working with arrays effectively. The declaration reserves a reference variable, while initialization allocates memory on the heap and assigns values.

Basic Declaration Syntax

In Java, you can declare arrays using square brackets either after the type or after the variable name. The preferred style is to place brackets after the type for clarity, as it keeps the type information together.

// Method 1: Declare then initialize (two steps)
int[] numbers;                    // Declaration: creates reference variable
numbers = new int[5];             // Initialization: allocates memory for 5 ints

// Method 2: Declare and initialize in one line (most common)
int[] scores = new int[10];       // Creates array of 10 integers (all default to 0)

// Method 3: Initialize with values (inline) — size is inferred
int[] primes = {2, 3, 5, 7, 11};  // Size is 5, automatically determined

// Method 4: Initialize with new keyword and values (explicit)
int[] fibonacci = new int[]{1, 1, 2, 3, 5, 8};

Method 1 is useful when you need to declare the array in one scope but initialize it later (like in a constructor). Method 2 is the most common approach for local variables. Method 3 is perfect when you know the exact values at compile time—Java counts the elements and sets the size automatically. Method 4 is required when passing an array directly to a method.

Common Array Types

Java supports arrays of any data type, including primitives, objects, and even other arrays (multidimensional).

// Primitive type arrays
int[] integers = new int[5];          // Default: 0
double[] decimals = new double[5];    // Default: 0.0
boolean[] flags = new boolean[5];     // Default: false
char[] characters = new char[5];      // Default: '\u0000' (null char)

// Object arrays
String[] names = new String[3];       // Default: null
Integer[] wrapped = new Integer[3];   // Default: null

// Initialize String array with values
String[] days = {"Mon", "Tue", "Wed", "Thu", "Fri"};

// Get array length (property, not method)
int length = days.length;  // 5 (no parentheses!)

Primitive arrays hold actual values directly in memory, making them more memory-efficient. Object arrays (like String[]) store references to objects, so each element points to a location elsewhere in heap memory. This distinction matters for understanding default values and memory usage.

Memory Visualization

Understanding how arrays are stored in memory helps you appreciate why access is O(1) and why resizing requires creating a new array.

int[] arr = {10, 20, 30, 40, 50};

// Address formula: address = base + (index × element_size)
// To access arr[2]:
//   address = 1000 + (2 × 4) = 1008  →  Value: 30

// This simple math is why array access is O(1)!
// No matter how big the array, finding any element takes the same time.

Arrays store elements in contiguous (side-by-side) memory locations. The JVM knows the base address and the size of each element, so accessing arr[i] is just simple arithmetic—no searching required. This is why random access is O(1), but also why you can't insert elements in the middle without shifting everything after it.

Mastering basic array operations is essential before moving to advanced techniques. These operations form the foundation for solving complex array problems and appear repeatedly in coding interviews.

Traversing Arrays

There are multiple ways to iterate through an array in Java. Each has its use case depending on whether you need the index, just the values, or need to modify elements during iteration.

int[] numbers = {10, 20, 30, 40, 50};

// Method 1: Traditional for loop (when you need index)
for (int i = 0; i < numbers.length; i++) {
    System.out.println("Index " + i + ": " + numbers[i]);
}

// Method 2: Enhanced for-each loop (when you only need values)
for (int num : numbers) {
    System.out.println(num);
}

// Method 3: Reverse traversal
for (int i = numbers.length - 1; i >= 0; i--) {
    System.out.println(numbers[i]);
}

// Method 4: While loop
int i = 0;
while (i < numbers.length) {
    System.out.println(numbers[i]);
    i++;
}

Common Array Operations

The java.util.Arrays class provides many utility methods for common array operations. These methods save you from writing boilerplate code and are highly optimized.

Printing Arrays: When you try to print an array directly using System.out.println(arr), Java doesn't show you the actual elements. Instead, it displays something cryptic like [I@1a2b3c4 — this is the array's type ([I means int array) followed by its memory address (hash code). This is almost never what you want! The solution is Arrays.toString(), which iterates through all elements and returns a nicely formatted string like [5, 2, 8, 1, 9]. For 2D arrays, use Arrays.deepToString() instead.

import java.util.Arrays;

int[] arr = {5, 2, 8, 1, 9};

// Without Arrays.toString() - prints memory address
System.out.println(arr);                    // [I@6d06d69c (not useful!)

// With Arrays.toString() - prints actual contents
System.out.println(Arrays.toString(arr));   // [5, 2, 8, 1, 9] ✓

Sorting Arrays: The Arrays.sort() method arranges elements in ascending order (smallest to largest). It's highly optimized — for primitive types like int[], Java uses Dual-Pivot Quicksort which has O(n log n) average time complexity. For object arrays like String[] or Integer[], it uses TimSort (a stable hybrid of merge sort and insertion sort). Warning: This method modifies the original array in-place! If you need to keep the original unchanged, create a copy first using Arrays.copyOf() before sorting. For descending order, you must use wrapper classes (Integer[] instead of int[]) with Collections.reverseOrder().

int[] arr = {5, 2, 8, 1, 9};

// Sort modifies the original array
Arrays.sort(arr);
System.out.println(Arrays.toString(arr));   // [1, 2, 5, 8, 9]

// For descending order, use Integer[] with Collections.reverseOrder()
Integer[] arr2 = {5, 2, 8, 1, 9};
Arrays.sort(arr2, Collections.reverseOrder());  // [9, 8, 5, 2, 1]

Binary Search: When you need to find whether an element exists in an array (and where), Arrays.binarySearch() is incredibly fast — it works in O(log n) time, meaning it can search through 1 million elements in just ~20 comparisons! The array must be sorted before calling this method, otherwise you'll get incorrect results. If the element is found, it returns the index. If not found, it returns a negative number: specifically -(insertion point) - 1, where insertion point is where the element would be inserted to maintain sorted order. This negative value is actually useful — you can calculate where to insert a new element!

int[] arr = {1, 2, 5, 8, 9};  // Must be sorted!

int index = Arrays.binarySearch(arr, 5);    // Returns 2 (index of 5)
int notFound = Arrays.binarySearch(arr, 7); // Returns -4 (negative = not found)

// The negative value indicates where the element would be inserted:
// -(insertion point) - 1

Filling Arrays: The Arrays.fill() method sets every element in an array to a specific value. This is extremely useful for initialization — for example, filling a distance array with Integer.MAX_VALUE for Dijkstra's algorithm, or resetting a visited array to false. You can also fill just a portion of the array by specifying a range fill(arr, fromIndex, toIndex, value) where fromIndex is inclusive and toIndex is exclusive (following Java's standard convention). Time complexity is O(n) where n is the number of elements being filled.

int[] zeros = new int[5];
Arrays.fill(zeros, 7);                      // [7, 7, 7, 7, 7]

// Fill only a range [fromIndex, toIndex)
int[] partial = new int[5];
Arrays.fill(partial, 1, 4, 9);              // [0, 9, 9, 9, 0]
//                   ^  ^
//                   |  └── toIndex (exclusive)
//                   └── fromIndex (inclusive)

Copying Arrays: Creating a true copy of an array is essential when you want to preserve the original data. Arrays.copyOf(arr, length) creates a new array with the specified length — if the new length is shorter, elements are truncated; if longer, the extra positions are filled with default values (0 for int, null for objects). Arrays.copyOfRange(arr, from, to) copies a specific slice of the array. Why this matters: In Java, arrays are objects stored in heap memory. When you write int[] b = a;, you're not copying the array — you're copying the reference (memory address). Both a and b now point to the same array, so changes through one variable affect the other. Use these copy methods to create an independent array.

int[] original = {1, 2, 5, 8, 9};

// Copy entire array
int[] copy = Arrays.copyOf(original, original.length);  // [1, 2, 5, 8, 9]

// Copy with different length (truncate or pad with zeros)
int[] shorter = Arrays.copyOf(original, 3);             // [1, 2, 5]
int[] longer = Arrays.copyOf(original, 7);              // [1, 2, 5, 8, 9, 0, 0]

// Copy a specific range [from, to)
int[] range = Arrays.copyOfRange(original, 1, 4);       // [2, 5, 8]

Comparing Arrays: A common mistake is using == to compare arrays — this only checks if two variables point to the exact same array object in memory, not whether they contain the same elements. Two arrays with identical content will return false with == if they're different objects! Use Arrays.equals(a, b) instead, which compares arrays element-by-element and returns true only if both arrays have the same length and all corresponding elements are equal. For multidimensional arrays (2D, 3D, etc.), use Arrays.deepEquals() which recursively compares nested arrays. Time complexity is O(n) where n is the array length.

int[] a = {1, 2, 3};
int[] b = {1, 2, 3};
int[] c = a;

// == compares references (memory addresses)
System.out.println(a == b);           // false (different objects)
System.out.println(a == c);           // true (same reference)

// Arrays.equals() compares content
System.out.println(Arrays.equals(a, b));  // true ✓ (same content)

// For 2D arrays, use deepEquals()
int[][] matrix1 = {{1, 2}, {3, 4}};
int[][] matrix2 = {{1, 2}, {3, 4}};
System.out.println(Arrays.deepEquals(matrix1, matrix2));  // true

Finding Min, Max, and Sum

These are the most common operations you will perform on arrays. Here are efficient implementations.

int[] arr = {5, 2, 8, 1, 9, 3};

// Find maximum
int max = arr[0];
for (int i = 1; i < arr.length; i++) {
    if (arr[i] > max) {
        max = arr[i];
    }
}
System.out.println("Max: " + max);  // 9

Finding the maximum value requires comparing each element against our current best candidate. We start by assuming the first element is the largest, then scan through the remaining elements. If we find a bigger number, it becomes our new maximum. This approach guarantees we check every element exactly once. Time: O(n) | Space: O(1)

// Find minimum
int min = arr[0];
for (int num : arr) {
    min = Math.min(min, num);
}
System.out.println("Min: " + min);  // 1

Finding the minimum follows the same logic as maximum, but we look for smaller values instead. Here we use Math.min() which returns the smaller of two numbers. This is cleaner than writing an if-statement and is commonly used in professional code. The enhanced for-loop makes the code more readable. Time: O(n) | Space: O(1)

// Calculate sum
int sum = 0;
for (int num : arr) {
    sum += num;
}
System.out.println("Sum: " + sum);  // 28

Calculating the sum is one of the most fundamental operations. We use an accumulator pattern: start with a sum of zero, then add each element to it. This pattern appears in countless algorithms including calculating averages, totals, and running sums. The enhanced for-loop is perfect here since we don't need the index. Time: O(n) | Space: O(1)

// Calculate average
double avg = (double) sum / arr.length;
System.out.println("Avg: " + avg);  // 4.666...

The average (mean) is calculated by dividing the sum by the count of elements. Important: we cast to double before dividing to get a decimal result. Without the cast, integer division would truncate the result (e.g., 28/6 would give 4 instead of 4.666...). This is a common source of bugs for beginners. Time: O(n) | Space: O(1)

void reverseArray(int[] arr) {
    int left = 0, right = arr.length - 1;
    
    while (left < right) {
        // Swap elements at left and right
        int temp = arr[left];
        arr[left] = arr[right];
        arr[right] = temp;
        
        left++;
        right--;
    }
}
// Time: O(n), Space: O(1)

int secondLargest(int[] arr) {
    if (arr.length < 2) {
        throw new IllegalArgumentException("Need at least 2 elements");
    }
    
    int first = Integer.MIN_VALUE;
    int second = Integer.MIN_VALUE;
    
    for (int num : arr) {
        if (num > first) {
            second = first;  // Old first becomes second
            first = num;     // Update first
        } else if (num > second && num != first) {
            second = num;    // Update second
        }
    }
    
    if (second == Integer.MIN_VALUE) {
        throw new IllegalArgumentException("No second largest");
    }
    return second;
}
// Time: O(n), Space: O(1)

void rotate(int[] nums, int k) {
    k = k % nums.length;  // Handle k > length
    
    // Reverse entire array
    reverse(nums, 0, nums.length - 1);
    // Reverse first k elements
    reverse(nums, 0, k - 1);
    // Reverse remaining elements
    reverse(nums, k, nums.length - 1);
}

void reverse(int[] arr, int start, int end) {
    while (start < end) {
        int temp = arr[start];
        arr[start] = arr[end];
        arr[end] = temp;
        start++;
        end--;
    }
}
// Time: O(n), Space: O(1)

void moveZeroes(int[] nums) {
    int insertPos = 0;  // Position to insert non-zero
    
    // Move all non-zero elements to the front
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] != 0) {
            nums[insertPos] = nums[i];
            insertPos++;
        }
    }
    
    // Fill remaining positions with zeros
    while (insertPos < nums.length) {
        nums[insertPos] = 0;
        insertPos++;
    }
}
// Time: O(n), Space: O(1)
// Example: [0,1,0,3,12] -> [1,3,12,0,0]

// Method 1: Using sum formula
int missingNumber(int[] nums) {
    int n = nums.length;
    int expectedSum = n * (n + 1) / 2;
    int actualSum = 0;
    
    for (int num : nums) {
        actualSum += num;
    }
    
    return expectedSum - actualSum;
}

// Method 2: Using XOR (handles overflow better)
int missingNumberXOR(int[] nums) {
    int xor = nums.length;  // Start with n
    
    for (int i = 0; i < nums.length; i++) {
        xor ^= i ^ nums[i];
    }
    
    return xor;
}
// Time: O(n), Space: O(1)
// Example: [3,0,1] -> 2 (missing from 0,1,2,3)

// Floyd's Cycle Detection (Tortoise and Hare)
int findDuplicate(int[] nums) {
    // Phase 1: Find intersection point
    int slow = nums[0];
    int fast = nums[0];
    
    do {
        slow = nums[slow];         // Move 1 step
        fast = nums[nums[fast]];   // Move 2 steps
    } while (slow != fast);
    
    // Phase 2: Find cycle entrance
    slow = nums[0];
    while (slow != fast) {
        slow = nums[slow];
        fast = nums[fast];
    }
    
    return slow;
}
// Time: O(n), Space: O(1)
// Example: [1,3,4,2,2] -> 2

int firstMissingPositive(int[] nums) {
    int n = nums.length;
    
    // Place each number in its correct position
    // nums[i] should be i+1
    for (int i = 0; i < n; i++) {
        while (nums[i] > 0 && nums[i] <= n 
               && nums[nums[i] - 1] != nums[i]) {
            // Swap nums[i] with nums[nums[i]-1]
            int correctIdx = nums[i] - 1;
            int temp = nums[i];
            nums[i] = nums[correctIdx];
            nums[correctIdx] = temp;
        }
    }
    
    // Find first position where nums[i] != i+1
    for (int i = 0; i < n; i++) {
        if (nums[i] != i + 1) {
            return i + 1;
        }
    }
    
    return n + 1;
}
// Time: O(n), Space: O(1)
// Example: [3,4,-1,1] -> 2

Searching is one of the most fundamental operations on arrays. The choice between linear and binary search depends on whether the array is sorted and the performance requirements.

Linear Search

Linear search (also called sequential search) checks each element one by one from the beginning until the target is found or the array ends. It's the simplest search algorithm and works on both sorted and unsorted arrays, but has O(n) time complexity.

// Linear Search - O(n) time, O(1) space
int linearSearch(int[] arr, int target) {
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] == target) {
            return i;  // Found at index i
        }
    }
    return -1;  // Not found
}

// Example usage
int[] nums = {64, 34, 25, 12, 22, 11, 90};
int index = linearSearch(nums, 22);  // Returns 4

The loop starts at index 0 and checks each element one by one. If arr[i] matches the target, we immediately return the index i where we found it—no need to check the rest!

If the loop completes without finding the target, we return -1 as a signal that the element doesn't exist in the array. This is a common convention since -1 is never a valid array index.

Binary Search

Binary search is dramatically faster at O(log n) but requires a sorted array. It repeatedly divides the search space in half by comparing the middle element with the target.

// Binary Search - O(log n) time, O(1) space
int binarySearch(int[] arr, int target) {
    int left = 0, right = arr.length - 1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;  // Prevents overflow
        
        if (arr[mid] == target) {
            return mid;           // Found!
        } else if (arr[mid] < target) {
            left = mid + 1;       // Search right half
        } else {
            right = mid - 1;      // Search left half
        }
    }
    return -1;  // Not found
}

// Example: Find 23 in [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
// Step 1: mid=16 < 23, search right
// Step 2: mid=56 > 23, search left  
// Step 3: mid=23 == 23, found at index 5!

We use two pointers, left and right, to track the current search range. Initially, the entire array is our search space. The loop continues as long as there's at least one element to check (left <= right).

Each iteration, we calculate the middle index and compare arr[mid] with our target. If they match, we're done! If the target is larger, it must be in the right half, so we move left past mid. If smaller, it's in the left half, so we move right before mid.

We use left + (right - left) / 2 instead of (left + right) / 2 to prevent integer overflow when both values are large. If the loop exits without finding the target, we return -1.

int[] searchRange(int[] nums, int target) {
    int[] result = {-1, -1};
    
    // Find first occurrence
    result[0] = findBound(nums, target, true);
    if (result[0] == -1) return result;
    
    // Find last occurrence
    result[1] = findBound(nums, target, false);
    return result;
}

int findBound(int[] nums, int target, boolean isFirst) {
    int left = 0, right = nums.length - 1;
    int bound = -1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (nums[mid] == target) {
            bound = mid;
            if (isFirst) {
                right = mid - 1;  // Keep searching left
            } else {
                left = mid + 1;   // Keep searching right
            }
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return bound;
}
// Time: O(log n), Space: O(1)
// Example: [5,7,7,8,8,10], target=8 -> [3,4]

int search(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (nums[mid] == target) return mid;
        
        // Check which half is sorted
        if (nums[left] <= nums[mid]) {
            // Left half is sorted
            if (target >= nums[left] && target < nums[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        } else {
            // Right half is sorted
            if (target > nums[mid] && target <= nums[right]) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
    }
    return -1;
}
// Time: O(log n), Space: O(1)
// Example: [4,5,6,7,0,1,2], target=0 -> 4

int findMin(int[] nums) {
    int left = 0, right = nums.length - 1;
    
    // Array is not rotated
    if (nums[left] < nums[right]) return nums[left];
    
    while (left < right) {
        int mid = left + (right - left) / 2;
        
        // If mid > right, min is in right half
        if (nums[mid] > nums[right]) {
            left = mid + 1;
        } else {
            // Min is at mid or in left half
            right = mid;
        }
    }
    return nums[left];
}
// Time: O(log n), Space: O(1)
// Example: [3,4,5,1,2] -> 1
// Example: [4,5,6,7,0,1,2] -> 0

int findPeakElement(int[] nums) {
    int left = 0, right = nums.length - 1;
    
    while (left < right) {
        int mid = left + (right - left) / 2;
        
        if (nums[mid] > nums[mid + 1]) {
            // Peak is at mid or to the left
            right = mid;
        } else {
            // Peak is to the right
            left = mid + 1;
        }
    }
    return left;  // left == right == peak
}
// Time: O(log n), Space: O(1)
// Example: [1,2,3,1] -> 2 (index of 3)
// Example: [1,2,1,3,5,6,4] -> 5 (index of 6)

int searchInsert(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (nums[mid] == target) {
            return mid;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return left;  // Insert position
}
// Time: O(log n), Space: O(1)
// Example: [1,3,5,6], target=5 -> 2 (found)
// Example: [1,3,5,6], target=2 -> 1 (insert position)

double findMedianSortedArrays(int[] nums1, int[] nums2) {
    // Ensure nums1 is smaller for binary search efficiency
    if (nums1.length > nums2.length) {
        return findMedianSortedArrays(nums2, nums1);
    }
    
    int m = nums1.length, n = nums2.length;
    int left = 0, right = m;
    
    while (left <= right) {
        int partitionX = (left + right) / 2;
        int partitionY = (m + n + 1) / 2 - partitionX;
        
        int maxLeftX = (partitionX == 0) ? Integer.MIN_VALUE : nums1[partitionX - 1];
        int minRightX = (partitionX == m) ? Integer.MAX_VALUE : nums1[partitionX];
        int maxLeftY = (partitionY == 0) ? Integer.MIN_VALUE : nums2[partitionY - 1];
        int minRightY = (partitionY == n) ? Integer.MAX_VALUE : nums2[partitionY];
        
        if (maxLeftX <= minRightY && maxLeftY <= minRightX) {
            // Found correct partition
            if ((m + n) % 2 == 0) {
                return (Math.max(maxLeftX, maxLeftY) + 
                        Math.min(minRightX, minRightY)) / 2.0;
            } else {
                return Math.max(maxLeftX, maxLeftY);
            }
        } else if (maxLeftX > minRightY) {
            right = partitionX - 1;
        } else {
            left = partitionX + 1;
        }
    }
    return 0.0;
}
// Time: O(log(min(m,n))), Space: O(1)
// Example: [1,3], [2] -> 2.0
// Example: [1,2], [3,4] -> 2.5

Sorting is a fundamental operation that arranges elements in a specific order (ascending or descending). Sorting is crucial because many algorithms (like binary search) require sorted data, and a well-chosen sort can simplify complex problems.

Using Arrays.sort()

Java's Arrays.sort() is highly optimized. It uses Dual-Pivot Quicksort for primitives (average O(n log n)) and TimSort for objects (a hybrid merge-insertion sort that's stable). In most cases, you should use these built-in methods rather than implementing your own sort.

import java.util.Arrays;
import java.util.Collections;

int[] arr = {5, 2, 8, 1, 9};

// Sort in ascending order
Arrays.sort(arr);  // [1, 2, 5, 8, 9]

// Sort a range (from index 1 to 4, exclusive)
int[] partial = {5, 2, 8, 1, 9};
Arrays.sort(partial, 1, 4);  // [5, 1, 2, 8, 9] - only middle sorted

// Sort in descending order (need Integer[], not int[])
Integer[] arr2 = {5, 2, 8, 1, 9};
Arrays.sort(arr2, Collections.reverseOrder());  // [9, 8, 5, 2, 1]

// Custom sorting with comparator
String[] names = {"Charlie", "Alice", "Bob"};
Arrays.sort(names);  // [Alice, Bob, Charlie] - alphabetical
Arrays.sort(names, (a, b) -> b.compareTo(a));  // [Charlie, Bob, Alice]

// Sort 2D array by first column
int[][] intervals = {{3, 5}, {1, 4}, {2, 6}};
Arrays.sort(intervals, (a, b) -> a[0] - b[0]);  // {{1,4}, {2,6}, {3,5}}

Basic Sorting Algorithms

While Arrays.sort() is preferred in production code, understanding basic sorting algorithms is essential for interviews. These O(n²) algorithms are simple to implement and help build intuition for more complex sorts.

1. Bubble Sort

void bubbleSort(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {
        boolean swapped = false;  // Optimization: detect if already sorted
        for (int j = 0; j < n - 1 - i; j++) {  // -i because last i elements are sorted
            if (arr[j] > arr[j + 1]) {
                // Swap adjacent elements
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                swapped = true;
            }
        }
        if (!swapped) break;  // Array is sorted, exit early
    }
}

// Example: [5, 2, 8, 1] → [2, 5, 1, 8] → [2, 1, 5, 8] → [1, 2, 5, 8]

The outer loop (i) controls the number of passes through the array. After each pass, the largest unsorted element is guaranteed to be in its final position, so we need at most n-1 passes.

The inner loop (j) compares adjacent elements. Notice n - 1 - i in the condition—this is an optimization that skips already-sorted elements at the end. After pass 1, the last element is sorted; after pass 2, the last 2 are sorted, and so on.

The swapped boolean is a clever optimization. If we complete an entire pass without any swaps, the array is already sorted and we can exit early. This gives bubble sort its best-case O(n) time complexity for already-sorted arrays.

2. Selection Sort

void selectionSort(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {
        int minIdx = i;  // Assume current position has minimum
        
        // Find actual minimum in unsorted portion
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIdx]) {
                minIdx = j;
            }
        }
        
        // Swap minimum to its correct position
        if (minIdx != i) {
            int temp = arr[i];
            arr[i] = arr[minIdx];
            arr[minIdx] = temp;
        }
    }
}

// Example: [5, 2, 8, 1] → [1, 2, 8, 5] → [1, 2, 8, 5] → [1, 2, 5, 8]

The outer loop (i) represents the current position we're trying to fill with the correct (minimum) element. It runs from 0 to n-2 because once we've placed n-1 elements, the last one is automatically in the right place.

We start by assuming the element at position i is the minimum (minIdx = i). The inner loop then scans through all remaining elements (j = i+1 to end) looking for anything smaller. If found, we update minIdx to track this new minimum's position.

After the inner loop completes, minIdx holds the position of the actual minimum in the unsorted portion. We then swap it with position i (only if needed, hence the if (minIdx != i) check). This ensures exactly one swap per pass, making selection sort efficient when swap operations are costly.

3. Insertion Sort

void insertionSort(int[] arr) {
    int n = arr.length;
    for (int i = 1; i < n; i++) {
        int key = arr[i];  // Element to insert
        int j = i - 1;
        
        // Shift elements greater than key to the right
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;  // Insert key at correct position
    }
}

// Example: [5, 2, 8, 1] → [2, 5, 8, 1] → [2, 5, 8, 1] → [1, 2, 5, 8]

We start from index 1 (not 0) because a single element is already "sorted" by itself. The outer loop picks each element as the key that needs to be inserted into the sorted portion to its left.

The while loop is where the magic happens. We compare the key with elements to its left, moving backwards (j--). For each element larger than key, we shift it one position right (arr[j+1] = arr[j]). This creates a "gap" that moves leftward until we find the right spot for key.

The loop stops when either we reach the beginning (j >= 0 fails) or we find an element smaller than or equal to key (arr[j] > key fails). We then insert key into the gap at position j + 1. This is why insertion sort is O(n) for nearly-sorted data—elements barely need to shift!

Imagine you're at a dance where two partners start at opposite ends of the dance floor and walk toward each other—or two runners start together but one runs faster than the other. That's the essence of the two pointer technique! It uses two index variables to traverse an array strategically, often from opposite ends or at different speeds. This elegant approach can transform slow O(n²) brute force solutions into lightning-fast O(n) optimal solutions—a skill that impresses interviewers!

Pattern 1: Opposite Ends

Start pointers at both ends and move them toward each other. Great for problems involving pairs in sorted arrays.

// Two Sum II - Input array is sorted
int[] twoSum(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};  // Found!
        } else if (sum < target) {
            left++;   // Need bigger sum
        } else {
            right--;  // Need smaller sum
        }
    }
    return new int[]{-1, -1};  // Not found
}

// Example: arr = [2, 7, 11, 15], target = 9
// Step 1: 2 + 15 = 17 > 9, move right
// Step 2: 2 + 11 = 13 > 9, move right
// Step 3: 2 + 7 = 9, found! Return [0, 1]

We place left at the start (smallest element) and right at the end (largest element). Since the array is sorted, arr[left] + arr[right] gives us the sum of smallest and largest available values.

If the sum is too small, we need a bigger number—so we move left right to get a larger value. If too big, we move right left to get a smaller value. The loop continues until pointers meet or we find the target.

Pattern 2: Fast and Slow

Both pointers start at the beginning. The slow pointer marks the position for valid elements while the fast pointer scans through the array.

// Remove Duplicates from Sorted Array
int removeDuplicates(int[] nums) {
    if (nums.length == 0) return 0;
    
    int slow = 0;  // Position for next unique element
    
    for (int fast = 1; fast < nums.length; fast++) {
        if (nums[fast] != nums[slow]) {
            slow++;
            nums[slow] = nums[fast];
        }
    }
    return slow + 1;  // Length of unique elements
}

// Example: [1, 1, 2, 2, 3] -> [1, 2, 3, _, _]
// Returns 3 (first 3 elements are unique)

The slow pointer marks the position where the next unique element should go. It stays at the last unique element we've placed. The fast pointer scans ahead looking for new unique values.

When fast finds a value different from nums[slow], we've found a new unique element! We increment slow to make room, then copy the new unique value there. Elements after slow don't matter—we return slow + 1 as the count of unique elements.

int maxArea(int[] height) {
    int left = 0, right = height.length - 1;
    int maxWater = 0;
    
    while (left < right) {
        int width = right - left;
        int h = Math.min(height[left], height[right]);
        maxWater = Math.max(maxWater, width * h);
        
        // Move the shorter line inward
        if (height[left] < height[right]) {
            left++;
        } else {
            right--;
        }
    }
    return maxWater;
}
// Time: O(n), Space: O(1)

boolean isPalindrome(String s) {
    int left = 0, right = s.length() - 1;
    
    while (left < right) {
        // Skip non-alphanumeric from left
        while (left < right && !Character.isLetterOrDigit(s.charAt(left))) {
            left++;
        }
        // Skip non-alphanumeric from right
        while (left < right && !Character.isLetterOrDigit(s.charAt(right))) {
            right--;
        }
        
        // Compare characters (case-insensitive)
        if (Character.toLowerCase(s.charAt(left)) != 
            Character.toLowerCase(s.charAt(right))) {
            return false;
        }
        left++;
        right--;
    }
    return true;
}
// Time: O(n), Space: O(1)
// Example: "A man, a plan, a canal: Panama" -> true

List> threeSum(int[] nums) {
    List> result = new ArrayList<>();
    Arrays.sort(nums);  // Sort first!
    
    for (int i = 0; i < nums.length - 2; i++) {
        // Skip duplicates for first element
        if (i > 0 && nums[i] == nums[i - 1]) continue;
        
        int left = i + 1, right = nums.length - 1;
        int target = -nums[i];
        
        while (left < right) {
            int sum = nums[left] + nums[right];
            
            if (sum == target) {
                result.add(Arrays.asList(nums[i], nums[left], nums[right]));
                
                // Skip duplicates
                while (left < right && nums[left] == nums[left + 1]) left++;
                while (left < right && nums[right] == nums[right - 1]) right--;
                
                left++;
                right--;
            } else if (sum < target) {
                left++;
            } else {
                right--;
            }
        }
    }
    return result;
}
// Time: O(n²), Space: O(1) excluding output
// Example: [-1,0,1,2,-1,-4] -> [[-1,-1,2],[-1,0,1]]

void sortColors(int[] nums) {
    int low = 0;              // Boundary for 0s
    int mid = 0;              // Current element
    int high = nums.length - 1;  // Boundary for 2s
    
    while (mid <= high) {
        if (nums[mid] == 0) {
            // Swap with low, move both pointers
            swap(nums, low, mid);
            low++;
            mid++;
        } else if (nums[mid] == 1) {
            // 1 is in correct position, just move mid
            mid++;
        } else {  // nums[mid] == 2
            // Swap with high, only move high
            swap(nums, mid, high);
            high--;
            // Don't increment mid, need to check swapped element
        }
    }
}

void swap(int[] nums, int i, int j) {
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}
// Time: O(n), Space: O(1)
// Example: [2,0,2,1,1,0] -> [0,0,1,1,2,2]

int[] sortedSquares(int[] nums) {
    int n = nums.length;
    int[] result = new int[n];
    int left = 0, right = n - 1;
    int pos = n - 1;  // Fill from end (largest first)
    
    while (left <= right) {
        int leftSq = nums[left] * nums[left];
        int rightSq = nums[right] * nums[right];
        
        if (leftSq > rightSq) {
            result[pos] = leftSq;
            left++;
        } else {
            result[pos] = rightSq;
            right--;
        }
        pos--;
    }
    return result;
}
// Time: O(n), Space: O(n)
// Example: [-4,-1,0,3,10] -> [0,1,9,16,100]

int trap(int[] height) {
    if (height.length == 0) return 0;
    
    int left = 0, right = height.length - 1;
    int leftMax = 0, rightMax = 0;
    int water = 0;
    
    while (left < right) {
        if (height[left] < height[right]) {
            // Water at left depends on leftMax
            if (height[left] >= leftMax) {
                leftMax = height[left];
            } else {
                water += leftMax - height[left];
            }
            left++;
        } else {
            // Water at right depends on rightMax
            if (height[right] >= rightMax) {
                rightMax = height[right];
            } else {
                water += rightMax - height[right];
            }
            right--;
        }
    }
    return water;
}
// Time: O(n), Space: O(1)
// Example: [0,1,0,2,1,0,1,3,2,1,2,1] -> 6

Picture looking out a train window as scenery passes by—you only see a portion of the landscape at any moment, but as the train moves, new views enter while old ones exit. That's exactly how the sliding window pattern works! It maintains a "window" over a contiguous subarray and efficiently slides it across the array. This brilliant technique transforms painfully slow O(n²) or O(n³) brute force solutions into elegant O(n) algorithms—one of the most satisfying optimizations in programming!

Fixed Size Window

When the window size is given, maintain the sum/property as you slide by adding the new element and removing the old one.

// Maximum Sum Subarray of Size K
int maxSumSubarray(int[] arr, int k) {
    if (arr.length < k) return -1;
    
    // Calculate sum of first window
    int windowSum = 0;
    for (int i = 0; i < k; i++) {
        windowSum += arr[i];
    }
    int maxSum = windowSum;
    
    // Slide the window
    for (int i = k; i < arr.length; i++) {
        windowSum += arr[i] - arr[i - k];  // Add new, remove old
        maxSum = Math.max(maxSum, windowSum);
    }
    return maxSum;
}

// Example: arr = [2, 1, 5, 1, 3, 2], k = 3
// Window [2,1,5] = 8
// Window [1,5,1] = 7  
// Window [5,1,3] = 9 (maximum!)
// Window [1,3,2] = 6

First, we calculate the sum of the initial window (first k elements) using a simple loop. This is our starting point and the first candidate for the maximum sum.

Then we slide the window one position at a time. The key insight: arr[i] is the new element entering the window, and arr[i - k] is the element leaving. Instead of recalculating the entire sum, we just add the new element and subtract the old one—a single operation per slide!

Variable Size Window

Unlike fixed-size windows where we know exactly how many elements to consider, variable size windows dynamically grow and shrink based on a condition. Think of it like a stretchy rubber band that expands until it catches what you're looking for, then contracts to find the optimal size.

Visual Example: Find Smallest Subarray with Sum ≥ 7

Array: [2, 3, 1, 2, 4, 3], Target: 7

Answer: Minimum length = 2 (subarray [4, 3])

// Minimum Size Subarray Sum >= target
int minSubArrayLen(int target, int[] nums) {
    int left = 0, sum = 0;
    int minLen = Integer.MAX_VALUE;
    
    for (int right = 0; right < nums.length; right++) {
        sum += nums[right];  // EXPAND: Add new element to window
        
        // SHRINK: While condition is satisfied, try to minimize
        while (sum >= target) {
            minLen = Math.min(minLen, right - left + 1);  // Record current valid window size
            sum -= nums[left];  // Remove leftmost element
            left++;             // Shrink window from left
        }
    }
    return minLen == Integer.MAX_VALUE ? 0 : minLen;
}
// Time: O(n) - each element visited at most twice (once by right, once by left)
// Space: O(1)

The right pointer expands the window by adding elements to sum. We keep expanding until our condition (sum >= target) is satisfied.

Once the condition is met, we enter the while loop to shrink. We record the current window size, then remove the leftmost element and move left forward. We keep shrinking as long as the condition remains satisfied—this finds the smallest valid window ending at the current right position.

The algorithm is O(n) because each element is added once (when right visits it) and removed at most once (when left passes it). Even though there's a while loop inside a for loop, the total operations are at most 2n.

double findMaxAverage(int[] nums, int k) {
    // Calculate sum of first window
    double windowSum = 0;
    for (int i = 0; i < k; i++) {
        windowSum += nums[i];
    }
    double maxSum = windowSum;
    
    // Slide the window
    for (int i = k; i < nums.length; i++) {
        windowSum += nums[i] - nums[i - k];
        maxSum = Math.max(maxSum, windowSum);
    }
    
    return maxSum / k;
}
// Time: O(n), Space: O(1)
// Example: nums = [1,12,-5,-6,50,3], k = 4 -> 12.75

int lengthOfLongestSubstring(String s) {
    Map charIndex = new HashMap<>();
    int maxLen = 0;
    int left = 0;
    
    for (int right = 0; right < s.length(); right++) {
        char c = s.charAt(right);
        
        // If char exists and is within current window
        if (charIndex.containsKey(c) && charIndex.get(c) >= left) {
            left = charIndex.get(c) + 1;  // Shrink window
        }
        
        charIndex.put(c, right);  // Update char position
        maxLen = Math.max(maxLen, right - left + 1);
    }
    
    return maxLen;
}
// Time: O(n), Space: O(min(m,n)) where m is charset size
// Example: "abcabcbb" -> 3 ("abc")

int longestOnes(int[] nums, int k) {
    int left = 0, maxLen = 0;
    int zeroCount = 0;
    
    for (int right = 0; right < nums.length; right++) {
        if (nums[right] == 0) {
            zeroCount++;
        }
        
        // Shrink window if too many zeros
        while (zeroCount > k) {
            if (nums[left] == 0) {
                zeroCount--;
            }
            left++;
        }
        
        maxLen = Math.max(maxLen, right - left + 1);
    }
    
    return maxLen;
}
// Time: O(n), Space: O(1)
// Example: nums = [1,1,1,0,0,0,1,1,1,1,0], k = 2 -> 6

int totalFruit(int[] fruits) {
    Map basket = new HashMap<>();
    int left = 0, maxFruits = 0;
    
    for (int right = 0; right < fruits.length; right++) {
        // Add fruit to basket
        basket.put(fruits[right], 
                   basket.getOrDefault(fruits[right], 0) + 1);
        
        // Shrink window if more than 2 types
        while (basket.size() > 2) {
            int leftFruit = fruits[left];
            basket.put(leftFruit, basket.get(leftFruit) - 1);
            if (basket.get(leftFruit) == 0) {
                basket.remove(leftFruit);
            }
            left++;
        }
        
        maxFruits = Math.max(maxFruits, right - left + 1);
    }
    
    return maxFruits;
}
// Time: O(n), Space: O(1) - at most 3 entries in map
// Example: [1,2,1] -> 3, [0,1,2,2] -> 3

String minWindow(String s, String t) {
    if (s.length() < t.length()) return "";
    
    // Count required characters
    Map required = new HashMap<>();
    for (char c : t.toCharArray()) {
        required.put(c, required.getOrDefault(c, 0) + 1);
    }
    
    int left = 0, minLen = Integer.MAX_VALUE, minStart = 0;
    int matched = 0;  // Number of unique chars matched
    Map window = new HashMap<>();
    
    for (int right = 0; right < s.length(); right++) {
        char c = s.charAt(right);
        window.put(c, window.getOrDefault(c, 0) + 1);
        
        // Check if this char is now fully matched
        if (required.containsKey(c) && 
            window.get(c).equals(required.get(c))) {
            matched++;
        }
        
        // Shrink window while valid
        while (matched == required.size()) {
            if (right - left + 1 < minLen) {
                minLen = right - left + 1;
                minStart = left;
            }
            
            char leftChar = s.charAt(left);
            window.put(leftChar, window.get(leftChar) - 1);
            if (required.containsKey(leftChar) && 
                window.get(leftChar) < required.get(leftChar)) {
                matched--;
            }
            left++;
        }
    }
    
    return minLen == Integer.MAX_VALUE ? "" : 
           s.substring(minStart, minStart + minLen);
}
// Time: O(s + t), Space: O(s + t)
// Example: s = "ADOBECODEBANC", t = "ABC" -> "BANC"

int[] maxSlidingWindow(int[] nums, int k) {
    if (nums.length == 0) return new int[0];
    
    int[] result = new int[nums.length - k + 1];
    // Deque stores indices, front has max element index
    Deque deque = new ArrayDeque<>();
    
    for (int i = 0; i < nums.length; i++) {
        // Remove indices outside current window
        while (!deque.isEmpty() && deque.peekFirst() < i - k + 1) {
            deque.pollFirst();
        }
        
        // Remove smaller elements (they can never be max)
        while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
            deque.pollLast();
        }
        
        deque.offerLast(i);
        
        // Window is complete, record max
        if (i >= k - 1) {
            result[i - k + 1] = nums[deque.peekFirst()];
        }
    }
    
    return result;
}
// Time: O(n), Space: O(k)
// Example: nums = [1,3,-1,-3,5,3,6,7], k = 3
// Output: [3,3,5,5,6,7]

Think of a spreadsheet like Excel—it has rows and columns, and you find any cell by its row number and column letter. A 2D array (also called a matrix) works exactly the same way! It's an array of arrays, commonly used to represent grids, tables, game boards (chess, sudoku), images (where each pixel is a cell), and graphs. Mastering 2D arrays is essential—they appear in 20-30% of coding interviews, especially in matrix manipulation, path finding, and dynamic programming problems.

Declaration and Traversal

1. Declaration and Initialization

There are two main ways to create a 2D array: specify dimensions with new, or initialize with values directly using curly braces.

// Method 1: Declare with dimensions (all values default to 0)
int[][] matrix = new int[3][4];  // 3 rows, 4 columns

// Method 2: Initialize with values (size is inferred)
int[][] grid = {
    {1, 2, 3},
    {4, 5, 6},
    {7, 8, 9}
};

2. Accessing Elements

Access any element using matrix[row][column]. Remember: indices are zero-based, so the first element is at [0][0].

int[][] grid = {
    {1, 2, 3},    // row 0
    {4, 5, 6},    // row 1
    {7, 8, 9}     // row 2
};

// Access element at row 1, column 2
int value = grid[1][2];  // Returns 6

// Modify an element
grid[0][0] = 10;  // First element is now 10

3. Getting Dimensions

Use .length to get the number of rows and columns. Remember: rows = outer array length, columns = inner array length.

int[][] grid = {
    {1, 2, 3},
    {4, 5, 6},
    {7, 8, 9}
};

// Get dimensions
int rows = grid.length;        // 3 (number of inner arrays)
int cols = grid[0].length;     // 3 (length of first inner array)

System.out.println("Matrix is " + rows + " x " + cols);  // "Matrix is 3 x 3"

4. Row-by-Row Traversal

The most common traversal pattern. The outer loop iterates through rows (i), and the inner loop iterates through columns (j). This reads left-to-right, top-to-bottom.

int[][] grid = {{1,2,3}, {4,5,6}, {7,8,9}};
int rows = grid.length;
int cols = grid[0].length;

// Row-by-row traversal (most common)
for (int i = 0; i < rows; i++) {           // For each row
    for (int j = 0; j < cols; j++) {       // For each column in row
        System.out.print(grid[i][j] + " ");
    }
    System.out.println();  // New line after each row
}

// Output:
// 1 2 3
// 4 5 6
// 7 8 9

5. Column-by-Column Traversal

Less common but useful for certain algorithms. Swap the loop order: outer loop for columns (j), inner loop for rows (i). This reads top-to-bottom, left-to-right.

int[][] grid = {{1,2,3}, {4,5,6}, {7,8,9}};
int rows = grid.length;
int cols = grid[0].length;

// Column-by-column traversal
for (int j = 0; j < cols; j++) {           // For each column
    for (int i = 0; i < rows; i++) {       // For each row in column
        System.out.print(grid[i][j] + " ");
    }
    System.out.println();  // New line after each column
}

// Output:
// 1 4 7  (column 0)
// 2 5 8  (column 1)
// 3 6 9  (column 2)

6. Enhanced For-Each Loop

When you don't need indices, the for-each loop provides cleaner syntax. The outer loop gives you each row (as a 1D array), and the inner loop gives you each element.

int[][] grid = {{1,2,3}, {4,5,6}, {7,8,9}};

// For-each traversal (when indices not needed)
for (int[] row : grid) {           // Each row is an int[]
    for (int value : row) {        // Each value in the row
        System.out.print(value + " ");
    }
    System.out.println();
}

// Output: Same as row-by-row
// 1 2 3
// 4 5 6
// 7 8 9

Common Matrix Operations

1. Transpose Matrix

Transposing a matrix means converting rows into columns and columns into rows. If the original matrix is m × n, the transposed matrix will be n × m. Element at position [i][j] moves to position [j][i].

// Transpose matrix (swap rows and columns)
int[][] transpose(int[][] matrix) {
    int rows = matrix.length;
    int cols = matrix[0].length;
    int[][] result = new int[cols][rows];  // Note: cols × rows
    
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            result[j][i] = matrix[i][j];  // Swap indices
        }
    }
    return result;
}
// Time: O(m × n), Space: O(m × n) for new matrix

2. Rotate Matrix 90° Clockwise

Rotating a matrix 90° clockwise is a common interview question. The trick is to break it into two simpler steps: transpose first, then reverse each row. This avoids complex index calculations.

Step 1: Transpose the matrix - Swap elements across the main diagonal.

// Step 1: Transpose (swap across main diagonal)
// Only swap upper triangle to avoid double-swapping
void transposeInPlace(int[][] matrix) {
    int n = matrix.length;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {  // j starts at i+1
            int temp = matrix[i][j];
            matrix[i][j] = matrix[j][i];
            matrix[j][i] = temp;
        }
    }
}
// Time: O(n²), Space: O(1) - in-place

Step 2: Reverse each row - Use two pointers to swap elements from ends toward center.

// Step 2: Reverse each row using two pointers
void reverseRows(int[][] matrix) {
    int n = matrix.length;
    for (int i = 0; i < n; i++) {
        int left = 0, right = n - 1;
        while (left < right) {
            int temp = matrix[i][left];
            matrix[i][left] = matrix[i][right];
            matrix[i][right] = temp;
            left++;
            right--;
        }
    }
}
// Time: O(n²), Space: O(1) - in-place

Complete Solution: Rotate 90° Clockwise

// Rotate matrix 90 degrees clockwise (in-place)
void rotate(int[][] matrix) {
    int n = matrix.length;
    
    // Step 1: Transpose
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            int temp = matrix[i][j];
            matrix[i][j] = matrix[j][i];
            matrix[j][i] = temp;
        }
    }
    
    // Step 2: Reverse each row
    for (int i = 0; i < n; i++) {
        int left = 0, right = n - 1;
        while (left < right) {
            int temp = matrix[i][left];
            matrix[i][left] = matrix[i][right];
            matrix[i][right] = temp;
            left++;
            right--;
        }
    }
}
// Time: O(n²), Space: O(1)

void printDiagonals(int[][] matrix) {
    int n = matrix.length;
    
    // Primary diagonal (top-left to bottom-right)
    System.out.print("Primary: ");
    for (int i = 0; i < n; i++) {
        System.out.print(matrix[i][i] + " ");
    }
    System.out.println();
    
    // Secondary diagonal (top-right to bottom-left)
    System.out.print("Secondary: ");
    for (int i = 0; i < n; i++) {
        System.out.print(matrix[i][n - 1 - i] + " ");
    }
}
// Time: O(n), Space: O(1)
// Example: [[1,2,3],[4,5,6],[7,8,9]]
// Primary: 1 5 9, Secondary: 3 5 7

List spiralOrder(int[][] matrix) {
    List result = new ArrayList<>();
    if (matrix.length == 0) return result;
    
    int top = 0, bottom = matrix.length - 1;
    int left = 0, right = matrix[0].length - 1;
    
    while (top <= bottom && left <= right) {
        // Traverse right
        for (int j = left; j <= right; j++) {
            result.add(matrix[top][j]);
        }
        top++;
        
        // Traverse down
        for (int i = top; i <= bottom; i++) {
            result.add(matrix[i][right]);
        }
        right--;
        
        // Traverse left (if row still exists)
        if (top <= bottom) {
            for (int j = right; j >= left; j--) {
                result.add(matrix[bottom][j]);
            }
            bottom--;
        }
        
        // Traverse up (if column still exists)
        if (left <= right) {
            for (int i = bottom; i >= top; i--) {
                result.add(matrix[i][left]);
            }
            left++;
        }
    }
    return result;
}
// Time: O(m*n), Space: O(1) excluding output
// Example: [[1,2,3],[4,5,6],[7,8,9]] -> [1,2,3,6,9,8,7,4,5]

void setZeroes(int[][] matrix) {
    int m = matrix.length, n = matrix[0].length;
    boolean firstRowZero = false, firstColZero = false;
    
    // Check if first row/col should be zero
    for (int j = 0; j < n; j++) {
        if (matrix[0][j] == 0) firstRowZero = true;
    }
    for (int i = 0; i < m; i++) {
        if (matrix[i][0] == 0) firstColZero = true;
    }
    
    // Use first row/col as markers
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            if (matrix[i][j] == 0) {
                matrix[i][0] = 0;  // Mark row
                matrix[0][j] = 0;  // Mark col
            }
        }
    }
    
    // Set zeros based on markers
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            if (matrix[i][0] == 0 || matrix[0][j] == 0) {
                matrix[i][j] = 0;
            }
        }
    }
    
    // Handle first row and column
    if (firstRowZero) {
        for (int j = 0; j < n; j++) matrix[0][j] = 0;
    }
    if (firstColZero) {
        for (int i = 0; i < m; i++) matrix[i][0] = 0;
    }
}
// Time: O(m*n), Space: O(1)

boolean searchMatrix(int[][] matrix, int target) {
    int m = matrix.length, n = matrix[0].length;
    
    // Treat as 1D sorted array
    int left = 0, right = m * n - 1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        // Convert 1D index to 2D
        int row = mid / n;
        int col = mid % n;
        int value = matrix[row][col];
        
        if (value == target) {
            return true;
        } else if (value < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return false;
}
// Time: O(log(m*n)), Space: O(1)
// Example: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]]
// target = 3 -> true

boolean searchMatrix(int[][] matrix, int target) {
    int m = matrix.length, n = matrix[0].length;
    
    // Start from top-right corner
    int row = 0, col = n - 1;
    
    while (row < m && col >= 0) {
        if (matrix[row][col] == target) {
            return true;
        } else if (matrix[row][col] > target) {
            col--;  // Move left (smaller values)
        } else {
            row++;  // Move down (larger values)
        }
    }
    return false;
}
// Time: O(m + n), Space: O(1)
// Key insight: From top-right, left is smaller, down is larger
// Example: target = 5 in:
// [[1,4,7,11],[2,5,8,12],[3,6,9,16],[10,13,14,17]]

int maximalRectangle(char[][] matrix) {
    if (matrix.length == 0) return 0;
    
    int n = matrix[0].length;
    int[] heights = new int[n];
    int maxArea = 0;
    
    for (int i = 0; i < matrix.length; i++) {
        // Build histogram heights for this row
        for (int j = 0; j < n; j++) {
            if (matrix[i][j] == '1') {
                heights[j]++;
            } else {
                heights[j] = 0;
            }
        }
        // Find max rectangle in histogram
        maxArea = Math.max(maxArea, largestRectangleInHistogram(heights));
    }
    return maxArea;
}

int largestRectangleInHistogram(int[] heights) {
    Stack stack = new Stack<>();
    int maxArea = 0;
    
    for (int i = 0; i <= heights.length; i++) {
        int h = (i == heights.length) ? 0 : heights[i];
        
        while (!stack.isEmpty() && h < heights[stack.peek()]) {
            int height = heights[stack.pop()];
            int width = stack.isEmpty() ? i : i - stack.peek() - 1;
            maxArea = Math.max(maxArea, height * width);
        }
        stack.push(i);
    }
    return maxArea;
}
// Time: O(m*n), Space: O(n)
// Builds on "Largest Rectangle in Histogram" problem