Arrays

What is an Array?

An array is a collection of elements stored at contiguous memory locations, each identified by at least one index. It's the most fundamental data structure in computer science, forming the basis for more complex data structures.

Speed:

Key Characteristics

Contiguous Memory O(1): Elements are stored in adjacent memory locations
Fixed Size: In traditional arrays, size is defined at creation
Homogeneous Elements: All elements typically have the same data type
Index-Based Access O(1): Elements can be directly accessed by their position

Types of Arrays

1. Static Arrays Fixed Size

Fixed-size arrays with size defined at compile time. Their size cannot be modified after creation.

// Static array in Java
int[] numbers = new int[5]; // Creates an array of size 5
numbers[0] = 10;
numbers[1] = 20;

// Or initialize with values
int[] scores = {85, 90, 78, 92, 88};

# Python doesn't have true static arrays, but you can use lists
numbers = [0] * 5  # Creates a list with 5 zeros
numbers[0] = 10
numbers[1] = 20

# Initialize with values
scores = [85, 90, 78, 92, 88]

// JavaScript doesn't have true static arrays, but you can use standard arrays
const numbers = new Array(5);  // Creates an array of size 5
numbers[0] = 10;
numbers[1] = 20;

// Or initialize with values
const scores = [85, 90, 78, 92, 88];

2. Dynamic Arrays Resizable

Resizable arrays that can grow or shrink during program execution. They handle memory management automatically.

Speed:

// Dynamic array in Java
import java.util.ArrayList;

ArrayList dynamicArray = new ArrayList<>();
dynamicArray.add(10);
dynamicArray.add(20);
dynamicArray.add(30);

// Add at specific position
dynamicArray.add(1, 15); // Inserts 15 at index 1

// Remove element
dynamicArray.remove(2); // Removes element at index 2

# Dynamic array in Python (lists are dynamic by default)
dynamic_array = []
dynamic_array.append(10)
dynamic_array.append(20)
dynamic_array.append(30)

# Add at specific position
dynamic_array.insert(1, 15) # Inserts 15 at index 1

# Remove element
dynamic_array.pop(2) # Removes element at index 2

// Dynamic array in JavaScript (arrays are dynamic by default)
const dynamicArray = [];
dynamicArray.push(10);
dynamicArray.push(20);
dynamicArray.push(30);

// Add at specific position
dynamicArray.splice(1, 0, 15); // Inserts 15 at index 1

// Remove element
dynamicArray.splice(2, 1); // Removes element at index 2

Memory Layout of Arrays

Arrays store elements in contiguous memory blocks, making them efficient for access but inflexible for dynamic operations.

How Arrays Work in Memory

Base Address: Memory address of the first element
Element Size: Each element occupies the same amount of memory
Index Calculation O(1): The address of an element at index i is calculated as:
address = base_address + (i * element_size)

Speed:

Memory Allocation

When an array is created, the system allocates a continuous block of memory:

Static Arrays: Memory is allocated at compile time and fixed
Dynamic Arrays: Memory is allocated at runtime and can grow as needed

Memory Consideration O(n): Resizing a dynamic array often requires allocating a new, larger block of memory and copying all elements, which is an expensive O(n) operation.

Array Operations Complexity

Operation	Time Complexity	Space Complexity	Notes
Access	O(1)	O(1)	Direct indexing allows constant-time access
Search (Unsorted)	O(n)	O(1)	Requires examining each element in worst case
Search (Sorted)	O(log n)	O(1)	Binary search can be applied
Insert (end)	O(1)*	O(1)	*O(1) on average for dynamic arrays
Insert (position)	O(n)	O(1)	Requires shifting elements
Delete (end)	O(1)	O(1)	Simple end pointer adjustment
Delete (position)	O(n)	O(1)	Requires shifting elements
Resize	O(n)	O(n)	Must copy elements to new array

Optimization Tip: When possible, add and remove elements from the end of an array to avoid the O(n) operations required for insertions and deletions at arbitrary positions.

Accessing Elements O(1)

One of the key advantages of arrays is constant-time O(1) access to any element using its index.

Speed:

// Access an element at index 2
int[] arr = {10, 20, 30, 40, 50};
int element = arr[2];  // element = 30

// Modify an element
arr[2] = 35;  // Now arr = {10, 20, 35, 40, 50}

# Access an element at index 2
arr = [10, 20, 30, 40, 50]
element = arr[2]  # element = 30

# Modify an element
arr[2] = 35  # Now arr = [10, 20, 35, 40, 50]

# Negative indices access from the end
last_element = arr[-1]  # last_element = 50

// Access an element at index 2
const arr = [10, 20, 30, 40, 50];
const element = arr[2];  // element = 30

// Modify an element
arr[2] = 35;  // Now arr = [10, 20, 35, 40, 50]

Watch out: Accessing an index out of bounds will cause runtime errors in most languages. Always validate indices before access.

Traversing Arrays O(n)

Traversing is the process of visiting each element in an array exactly once, typically to perform some operation on each element.

Speed:

Common Traversal Patterns

// 1. Using for loop with index
int[] arr = {5, 9, 3, 7, 2};
for (int i = 0; i < arr.length; i++) {
    System.out.println("Element at index " + i + ": " + arr[i]);
}

// 2. Using enhanced for loop (for-each)
for (int element : arr) {
    System.out.println("Element: " + element);
}

// 3. Traversing in reverse
for (int i = arr.length - 1; i >= 0; i--) {
    System.out.println("Element at index " + i + ": " + arr[i]);
}

# 1. Using for loop with index
arr = [5, 9, 3, 7, 2]
for i in range(len(arr)):
    print(f"Element at index {i}: {arr[i]}")

# 2. Using for-each loop
for element in arr:
    print(f"Element: {element}")

# 3. Using enumerate for both index and value
for i, element in enumerate(arr):
    print(f"Element at index {i}: {element}")

# 4. Traversing in reverse
for i in range(len(arr) - 1, -1, -1):
    print(f"Element at index {i}: {arr[i]}")

# Alternative reverse using reversed()
for element in reversed(arr):
    print(f"Element: {element}")

// 1. Using for loop with index
const arr = [5, 9, 3, 7, 2];
for (let i = 0; i < arr.length; i++) {
    console.log(`Element at index ${i}: ${arr[i]}`);
}

// 2. Using for...of loop (ES6+)
for (const element of arr) {
    console.log(`Element: ${element}`);
}

// 3. Using forEach method
arr.forEach((element, index) => {
    console.log(`Element at index ${index}: ${element}`);
});

// 4. Traversing in reverse
for (let i = arr.length - 1; i >= 0; i--) {
    console.log(`Element at index ${i}: ${arr[i]}`);
}

Performance Tip: For large arrays, a simple for loop with an index is often the most performant traversal method in most languages.

Inserting Elements

Insertion operations add new elements to an array, either at the end or at a specific position.

Speed:

Insertion Operations

// For static arrays, insertion requires manual element shifting
// Insert at a specific position (index 2)
int[] arr = {10, 20, 30, 40, 0}; // Last element as placeholder
int insertPos = 2;
int newValue = 25;

// Shift elements to make room
for (int i = arr.length - 1; i > insertPos; i--) {
    arr[i] = arr[i - 1];
}
arr[insertPos] = newValue; // Insert the new element

// For dynamic arrays (ArrayList)
import java.util.ArrayList;
ArrayList list = new ArrayList<>();
list.add(10);        // Append to end: [10]
list.add(20);        // Append to end: [10, 20]
list.add(1, 15);     // Insert at index 1: [10, 15, 20]
list.add(0, 5);      // Insert at beginning: [5, 10, 15, 20]

# Python lists (dynamic arrays)

# 1. Append to end (O(1) on average)
arr = [10, 20, 30, 40]
arr.append(50)  # arr becomes [10, 20, 30, 40, 50]

# 2. Insert at specific position (O(n))
arr.insert(2, 25)  # arr becomes [10, 20, 25, 30, 40, 50]

# 3. Insert at beginning (O(n))
arr.insert(0, 5)  # arr becomes [5, 10, 20, 25, 30, 40, 50]

# 4. Extend with multiple elements at once
arr.extend([60, 70])  # arr becomes [5, 10, 20, 25, 30, 40, 50, 60, 70]

// JavaScript arrays (dynamic arrays)

// 1. Append to end (O(1) on average)
let arr = [10, 20, 30, 40];
arr.push(50);  // arr becomes [10, 20, 30, 40, 50]

// 2. Insert at specific position (O(n))
arr.splice(2, 0, 25);  // arr becomes [10, 20, 25, 30, 40, 50]

// 3. Insert at beginning (O(n))
arr.unshift(5);  // arr becomes [5, 10, 20, 25, 30, 40, 50]

// 4. Concatenate arrays
arr = arr.concat([60, 70]);  // arr becomes [5, 10, 20, 25, 30, 40, 50, 60, 70]

Efficiency Tip: Inserting at the end of an array is generally O(1) on average, while inserting at the beginning or middle is O(n) due to element shifting.

Deleting Elements

Deletion operations remove elements from an array, either from the end, beginning, or a specific position.

Speed:

Deletion Operations

// For static arrays, deletion requires manual element shifting
// Delete from a specific position (index 2)
int[] arr = {15, 30, 45, 60, 75};
int deletePos = 2;

// Shift elements to fill the gap
for (int i = deletePos; i < arr.length - 1; i++) {
    arr[i] = arr[i + 1];
}
arr[arr.length - 1] = 0; // Optional: Clear the last element

// For dynamic arrays (ArrayList)
import java.util.ArrayList;
ArrayList list = new ArrayList<>();
list.add(15);
list.add(30);
list.add(45);
list.add(60);
list.add(75);

list.remove(2);             // Remove by index: [15, 30, 60, 75]
list.remove(list.size()-1); // Remove last element: [15, 30, 60]
list.remove(0);             // Remove first element: [30, 60]

// Remove by value
Integer valueToRemove = 30;
list.remove(valueToRemove); // Remove 30: [60]

# Python lists (dynamic arrays)

# 1. Remove from end (O(1))
arr = [15, 30, 45, 60, 75]
arr.pop()  # Removes 75, arr becomes [15, 30, 45, 60]

# 2. Remove from specific position (O(n))
del arr[2]  # Removes 45, arr becomes [15, 30, 60]
# Alternative: arr.pop(2)

# 3. Remove from beginning (O(n))
arr.pop(0)  # Removes 15, arr becomes [30, 60]

# 4. Remove by value (first occurrence)
arr = [15, 30, 45, 30, 60]
arr.remove(30)  # Removes first 30, arr becomes [15, 45, 30, 60]

# 5. Clear all elements
arr.clear()  # arr becomes []

// JavaScript arrays (dynamic arrays)

// 1. Remove from end (O(1))
let arr = [15, 30, 45, 60, 75];
arr.pop();  // Removes 75, arr becomes [15, 30, 45, 60]

// 2. Remove from specific position (O(n))
arr.splice(2, 1);  // Removes 45, arr becomes [15, 30, 60]

// 3. Remove from beginning (O(n))
arr.shift();  // Removes 15, arr becomes [30, 60]

// 4. Remove multiple elements
arr = [15, 30, 45, 60, 75];
arr.splice(1, 3);  // Removes 3 elements starting at index 1
                  // arr becomes [15, 75]

// 5. Remove by value (filter creates a new array)
arr = [15, 30, 45, 30, 60];
arr = arr.filter(element => element !== 30);  // arr becomes [15, 45, 60]

Performance Note: Deleting elements from the beginning or middle of an array requires shifting subsequent elements, resulting in O(n) time complexity.

Searching in Arrays

Searching operations locate specific elements within an array, with efficiency depending on whether the array is sorted.

Linear Search O(n)

Examines each element sequentially until the target is found or the end is reached. Works on both sorted and unsorted arrays.

Speed:

Linear Search Time: O(n) | Space: O(1)

// Linear search implementation
public int linearSearch(int[] arr, int target) {
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] == target) {
            return i; // Return index if found
        }
    }
    return -1;  // Return -1 if not found
}

# Linear search implementation
def linear_search(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i  # Return index if found
    return -1  # Return -1 if not found

# Python also has built-in methods:
# - Use 'in' operator to check existence
if target in arr:
    # Use index() to get position (raises ValueError if not found)
    position = arr.index(target)

// Linear search implementation
function linearSearch(arr, target) {
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] === target) {
            return i;  // Return index if found
        }
    }
    return -1;  // Return -1 if not found
}

// JavaScript also has built-in methods:
// - indexOf returns index or -1 if not found
const index = arr.indexOf(target);

// - includes returns true/false
const exists = arr.includes(target);

Binary Search O(log n)

A divide-and-conquer algorithm that works only on sorted arrays. It repeatedly divides the search interval in half, achieving logarithmic time complexity.

Speed:

Binary Search Time: O(log n) | Space: O(1)

// Binary search implementation (iterative)
public int binarySearch(int[] arr, int target) {
    int left = 0;
    int right = arr.length - 1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;  // Prevents overflow
        
        // Check if target is present at mid
        if (arr[mid] == target) {
            return mid;
        }
        
        // If target is greater, ignore left half
        if (arr[mid] < target) {
            left = mid + 1;
        } 
        // If target is smaller, ignore right half
        else {
            right = mid - 1;
        }
    }
    
    return -1;  // Target not found
}

// Java also provides built-in binary search:
// int index = Arrays.binarySearch(arr, target);

# Binary search implementation (iterative)
def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    
    while left <= right:
        mid = left + (right - left) // 2
        
        # Check if target is present at mid
        if arr[mid] == target:
            return mid
        
        # If target is greater, ignore left half
        elif arr[mid] < target:
            left = mid + 1
        
        # If target is smaller, ignore right half
        else:
            right = mid - 1
            
    return -1  # Target not found

# Python's bisect module can be used for binary search:
import bisect
# Find insertion point (doesn't confirm existence)
index = bisect.bisect_left(arr, target)
# Check if target exists
if index < len(arr) and arr[index] == target:
    print(f"Found at index {index}")

// Binary search implementation (iterative)
function binarySearch(arr, target) {
    let left = 0;
    let right = arr.length - 1;
    
    while (left <= right) {
        const mid = Math.floor(left + (right - left) / 2);
        
        // Check if target is present at mid
        if (arr[mid] === target) {
            return mid;
        }
        
        // If target is greater, ignore left half
        if (arr[mid] < target) {
            left = mid + 1;
        } 
        // If target is smaller, ignore right half
        else {
            right = mid - 1;
        }
    }
    
    return -1;  // Target not found
}

When to use: For sorted arrays, always prefer binary search (O(log n)) over linear search (O(n)). For small arrays (n < 20) or unsorted arrays, linear search might be more practical.

Binary Search Algorithm O(log n)

Binary Search is an efficient algorithm for finding a target value within a sorted array. It works by repeatedly dividing the search interval in half.

How Binary Search Works

The algorithm compares the target value to the middle element of the array:

If the target matches the middle element, the search is successful
If the target is less than the middle element, the search continues in the lower half
If the target is greater than the middle element, the search continues in the upper half

This process continues until the target is found or the subarray is empty.

Speed:

Implementation

Binary Search Time: O(log n) | Space: O(1)

// Binary search implementation (iterative)
public int binarySearch(int[] arr, int target) {
    int left = 0;
    int right = arr.length - 1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;  // Prevents overflow
        
        // Check if target is present at mid
        if (arr[mid] == target) {
            return mid;
        }
        
        // If target is greater, ignore left half
        if (arr[mid] < target) {
            left = mid + 1;
        } 
        // If target is smaller, ignore right half
        else {
            right = mid - 1;
        }
    }
    
    return -1;  // Target not found
}

# Binary search implementation (iterative)
def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    
    while left <= right:
        mid = left + (right - left) // 2
        
        # Check if target is present at mid
        if arr[mid] == target:
            return mid
        
        # If target is greater, ignore left half
        elif arr[mid] < target:
            left = mid + 1
        
        # If target is smaller, ignore right half
        else:
            right = mid - 1
            
    return -1  # Target not found

// Binary search implementation (iterative)
function binarySearch(arr, target) {
    let left = 0;
    let right = arr.length - 1;
    
    while (left <= right) {
        const mid = Math.floor(left + (right - left) / 2);
        
        // Check if target is present at mid
        if (arr[mid] === target) {
            return mid;
        }
        
        // If target is greater, ignore left half
        if (arr[mid] < target) {
            left = mid + 1;
        } 
        // If target is smaller, ignore right half
        else {
            right = mid - 1;
        }
    }
    
    return -1;  // Target not found
}

When to use Binary Search:

The collection must be sorted
Random access is available (like in arrays)
The collection is large enough that linear search would be inefficient
The data doesn't change frequently (or can be re-sorted efficiently)

Time Complexity Analysis

Best Case: O(1) - Target is at the middle position
Average Case: O(log n) - Dividing search interval in half each time
Worst Case: O(log n) - Target is at the extreme ends or not present

Common Mistakes:

Calculating the middle index as (left + right) / 2 can lead to integer overflow in some languages
Incorrectly defining the end condition (should be left <= right)
Using binary search on an unsorted array

Two Pointer Technique O(n)

A technique that uses two pointers to solve array problems efficiently, typically reducing time complexity from O(n²) to O(n).

Pointers start from opposite ends of the array and move toward each other.

Speed:

Generic Template

Two Pointers (Opposite Directions) Time: O(n) | Space: O(1)

// Two pointers starting from opposite ends
public void twoPointersOpposite(int[] arr, int target) {
    int left = 0;
    int right = arr.length - 1;
    
    while (left < right) {
        int sum = arr[left] + arr[right];
        
        // Process arr[left] and arr[right]
        if (sum == target) {
            // Found the target
            System.out.println("Found pair: " + arr[left] + ", " + arr[right]);
            return;
        }
        
        // Move pointers based on comparison
        if (sum > target) {
            right--; // Need a smaller value
        } else {
            left++; // Need a larger value
        }
    }
    
    System.out.println("No solution found");
}

# Two pointers starting from opposite ends
def two_pointers_opposite(arr, target):
    left, right = 0, len(arr) - 1
    
    while left < right:
        current_sum = arr[left] + arr[right]
        
        # Process arr[left] and arr[right]
        if current_sum == target:
            # Found the target
            print(f"Found pair: {arr[left]}, {arr[right]}")
            return [left, right]
        
        # Move pointers based on comparison
        if current_sum > target:
            right -= 1  # Need a smaller value
        else:
            left += 1   # Need a larger value
    
    print("No solution found")
    return None

// Two pointers starting from opposite ends
function twoPointersOpposite(arr, target) {
    let left = 0;
    let right = arr.length - 1;
    
    while (left < right) {
        const sum = arr[left] + arr[right];
        
        // Process arr[left] and arr[right]
        if (sum === target) {
            // Found the target
            console.log(`Found pair: ${arr[left]}, ${arr[right]}`);
            return [left, right];
        }
        
        // Move pointers based on comparison
        if (sum > target) {
            right--; // Need a smaller value
        } else {
            left++;  // Need a larger value
        }
    }
    
    console.log("No solution found");
    return null;
}

Common Problems

Two Sum: Find a pair of numbers that add up to a target (in sorted array)
Container With Most Water: Find two lines that together with x-axis form a container that holds the most water
Palindrome Verification: Check if a string is a palindrome
Reverse Array: Reverse an array in-place
3Sum/4Sum: Finding triplets/quadruplets that satisfy certain conditions

How to Identify: Consider using the two pointer technique when:

You need to find a pair of elements in a sorted array that satisfy some condition
You need to compare elements from both ends of an array
The problem involves checking for palindromes or symmetry
You're searching for a pair with a specific sum, product, or difference
You need to find the smallest/largest value satisfying a condition

Both pointers move in the same direction but at different paces or with different conditions.

Speed:

Generic Template

Two Pointers (Same Direction) Time: O(n) | Space: O(1)

// Two pointers moving in same direction (remove duplicates example)
public int removeDuplicates(int[] nums) {
    if (nums.length == 0) return 0;
    
    int slow = 0; // Position to place next unique element
    
    for (int fast = 1; fast < nums.length; fast++) {
        // If current element is different from previous
        if (nums[fast] != nums[slow]) {
            slow++; // Move slow pointer
            nums[slow] = nums[fast]; // Update array in-place
        }
        // If duplicate, only fast pointer moves
    }
    
    // Return new length (slow + 1 elements)
    return slow + 1;
}

# Two pointers moving in same direction (remove duplicates example)
def remove_duplicates(nums):
    if not nums:
        return 0
    
    slow = 0  # Position to place next unique element
    
    for fast in range(1, len(nums)):
        # If current element is different from previous
        if nums[fast] != nums[slow]:
            slow += 1  # Move slow pointer
            nums[slow] = nums[fast]  # Update array in-place
        # If duplicate, only fast pointer moves
    
    # Return new length (slow + 1 elements)
    return slow + 1

// Two pointers moving in same direction (remove duplicates example)
function removeDuplicates(nums) {
    if (nums.length === 0) return 0;
    
    let slow = 0; // Position to place next unique element
    
    for (let fast = 1; fast < nums.length; fast++) {
        // If current element is different from previous
        if (nums[fast] !== nums[slow]) {
            slow++; // Move slow pointer
            nums[slow] = nums[fast]; // Update array in-place
        }
        // If duplicate, only fast pointer moves
    }
    
    // Return new length (slow + 1 elements)
    return slow + 1;
}

Common Problems

Remove Duplicates: Remove duplicates from a sorted array
Move Zeroes: Move all zeroes to the end while maintaining the order of other elements
Remove Element: Remove all instances of a given value from an array
Merge Sorted Arrays: Merge two sorted arrays into one

How to Identify: Consider using same-direction two pointers when:

You need to process elements sequentially while keeping track of a specific condition
You're dealing with a sorted array where you need to remove or identify specific values
You need to maintain two separate parts of an array (e.g., processed and unprocessed sections)
A fast pointer needs to "scout ahead" while a slow pointer tracks a position of interest
You need to detect cycles in linked lists (fast and slow pointers)

Sliding Window Technique O(n)

An efficient algorithmic technique used to process contiguous subarrays or sublists, typically converting O(n²) approaches to O(n).

Speed:

Window Size:

Generic Template

Fixed Size Sliding Window Time: O(n) | Space: O(1)

// Fixed size sliding window - Maximum sum subarray of size k
public int maxSumSubarray(int[] arr, int k) {
    // Handle edge cases
    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 window from left to right
    for (int i = k; i < arr.length; i++) {
        // Add incoming element, remove outgoing element
        windowSum = windowSum + arr[i] - arr[i - k];
        
        // Update maximum sum
        maxSum = Math.max(maxSum, windowSum);
    }
    
    return maxSum;
}

# Fixed size sliding window - Maximum sum subarray of size k
def max_sum_subarray(arr, k):
    # Handle edge cases
    if len(arr) < k:
        return -1
    
    # Calculate sum of first window
    window_sum = sum(arr[:k])
    max_sum = window_sum
    
    # Slide window from left to right
    for i in range(k, len(arr)):
        # Add incoming element, remove outgoing element
        window_sum = window_sum + arr[i] - arr[i - k]
        
        # Update maximum sum
        max_sum = max(max_sum, window_sum)
    
    return max_sum

// Fixed size sliding window - Maximum sum subarray of size k
function maxSumSubarray(arr, k) {
    // Handle edge cases
    if (arr.length < k) return -1;
    
    // Calculate sum of first window
    let windowSum = 0;
    for (let i = 0; i < k; i++) {
        windowSum += arr[i];
    }
    
    let maxSum = windowSum;
    
    // Slide window from left to right
    for (let i = k; i < arr.length; i++) {
        // Add incoming element, remove outgoing element
        windowSum = windowSum + arr[i] - arr[i - k];
        
        // Update maximum sum
        maxSum = Math.max(maxSum, windowSum);
    }
    
    return maxSum;
}

Common Problems

Maximum/Minimum Sum Subarray of Size K: Find the subarray of size K with the maximum/minimum sum
Count Occurrences of Anagrams: Count occurrences of all anagrams of a pattern in a string
Maximum of All Subarrays of Size K: Find maximum element in each subarray of size K
First Negative Number in Every Window of Size K: Find the first negative integer in each sliding window

How to Identify: Consider using fixed-size sliding window when:

You need to process subarrays/substrings of a specific size k
You're asked to find maximum/minimum/average of all subarrays of size k
You need to calculate something for every contiguous segment of fixed size
The problem involves finding patterns of exact length k

Speed:

Target Sum:

Generic Template

Variable Size Sliding Window Time: O(n) | Space: O(1) or O(k)

// Variable size sliding window - Smallest subarray with sum >= target
public int minSubArrayLen(int[] nums, int target) {
    int minLength = Integer.MAX_VALUE;
    int windowSum = 0;
    int windowStart = 0;
    
    for (int windowEnd = 0; windowEnd < nums.length; windowEnd++) {
        // Expand the window by including the current element
        windowSum += nums[windowEnd];
        
        // Shrink the window as small as possible while maintaining the sum >= target
        while (windowSum >= target) {
            // Update minimum length
            minLength = Math.min(minLength, windowEnd - windowStart + 1);
            
            // Remove leftmost element from the window
            windowSum -= nums[windowStart];
            windowStart++;
        }
    }
    
    // If we didn't find any window with sum >= target
    return minLength == Integer.MAX_VALUE ? 0 : minLength;
}

# Variable size sliding window - Smallest subarray with sum >= target
def min_subarray_len(nums, target):
    min_length = float('inf')
    window_sum = 0
    window_start = 0
    
    for window_end in range(len(nums)):
        # Expand the window by including the current element
        window_sum += nums[window_end]
        
        # Shrink the window as small as possible while maintaining the sum >= target
        while window_sum >= target:
            # Update minimum length
            min_length = min(min_length, window_end - window_start + 1)
            
            # Remove leftmost element from the window
            window_sum -= nums[window_start]
            window_start += 1
    
    # If we didn't find any window with sum >= target
    return 0 if min_length == float('inf') else min_length

// Variable size sliding window - Smallest subarray with sum >= target
function minSubArrayLen(nums, target) {
    let minLength = Infinity;
    let windowSum = 0;
    let windowStart = 0;
    
    for (let windowEnd = 0; windowEnd < nums.length; windowEnd++) {
        // Expand the window by including the current element
        windowSum += nums[windowEnd];
        
        // Shrink the window as small as possible while maintaining the sum >= target
        while (windowSum >= target) {
            // Update minimum length
            minLength = Math.min(minLength, windowEnd - windowStart + 1);
            
            // Remove leftmost element from the window
            windowSum -= nums[windowStart];
            windowStart++;
        }
    }
    
    // If we didn't find any window with sum >= target
    return minLength === Infinity ? 0 : minLength;
}

Common Problems

Minimum Size Subarray Sum: Find the minimum length subarray with a sum greater than or equal to target
Longest Substring Without Repeating Characters: Find the length of the longest substring without repeating characters
Longest Substring with K Distinct Characters: Find the longest substring with at most k distinct characters
Fruits into Baskets: Collect maximum fruits from a tree where you can only have 2 types of fruits

How to Identify: Consider using variable-size sliding window when:

You need to find a subarray that satisfies a specific condition (e.g., sum >= target)
You need to find the longest/shortest subarray that meets a specific criterion
You're working with problems involving substring constraints (like at most k distinct characters)
The problem has a "minimizing" or "maximizing" aspect to continuous segments
The problem involves some constraint that can be satisfied by expanding or contracting a window

Key Insight: In variable size windows, expand the window by adding elements until you satisfy a condition, then contract it by removing elements until the condition is no longer satisfied.

Prefix Sum Technique O(1) queries after O(n) preprocessing

A preprocessing technique that allows fast calculation of sum of elements in a given range. It precomputes cumulative sums to enable O(1) range sum queries.

Speed:

How It Works

The prefix sum array prefix[i] contains the sum of all elements from arr[0] to arr[i]. This allows us to compute the sum of any range [i, j] as prefix[j] - prefix[i-1] in O(1) time.

Generic Template

Prefix Sum Precomputation: O(n) | Query: O(1)

// Compute prefix sum array
public int[] buildPrefixSum(int[] arr) {
    int n = arr.length;
    int[] prefix = new int[n];
    
    // First element is the same
    prefix[0] = arr[0];
    
    // Compute cumulative sum
    for (int i = 1; i < n; i++) {
        prefix[i] = prefix[i-1] + arr[i];
    }
    
    return prefix;
}

// Query the sum of range [left, right]
public int rangeSum(int[] prefix, int left, int right) {
    if (left == 0) {
        return prefix[right];
    } else {
        return prefix[right] - prefix[left-1];
    }
}

# Compute prefix sum array
def build_prefix_sum(arr):
    n = len(arr)
    prefix = [0] * n
    
    # First element is the same
    prefix[0] = arr[0]
    
    # Compute cumulative sum
    for i in range(1, n):
        prefix[i] = prefix[i-1] + arr[i]
    
    return prefix

# Query the sum of range [left, right]
def range_sum(prefix, left, right):
    if left == 0:
        return prefix[right]
    else:
        return prefix[right] - prefix[left-1]

// Compute prefix sum array
function buildPrefixSum(arr) {
    const n = arr.length;
    const prefix = new Array(n);
    
    // First element is the same
    prefix[0] = arr[0];
    
    // Compute cumulative sum
    for (let i = 1; i < n; i++) {
        prefix[i] = prefix[i-1] + arr[i];
    }
    
    return prefix;
}

// Query the sum of range [left, right]
function rangeSum(prefix, left, right) {
    if (left === 0) {
        return prefix[right];
    } else {
        return prefix[right] - prefix[left-1];
    }
}

Common Problems

Range Sum Queries: Find the sum of all elements in a given range
Subarray Sum Equals K: Find number of subarrays with sum equal to K
Maximum Subarray Sum: Find the subarray with the largest sum
Number of Subarrays with Sum Divisible by K: Count subarrays with sum divisible by K
Product of Array Except Self: Calculate product of all elements except the current one

How to Identify: Consider using prefix sums when:

You need to calculate multiple range sums efficiently
You're repeatedly querying for sums over different ranges of an array
You need to find all subarrays with a specific sum
The problem involves cumulative properties (sum, product, XOR, etc.) over ranges
You see phrases like "find the number of subarrays that..." or "find the total of all subarrays that..."

Performance Tip: For multiple range sum queries, it's almost always more efficient to precompute the prefix sum once (O(n)) and then answer each query in O(1) time rather than computing each range sum directly (O(n) per query).

Kadane's Algorithm O(n)

A dynamic programming approach to find the maximum sum subarray in an array containing both positive and negative numbers, with O(n) time complexity.

-2

-3

-1

-5

Speed:

How It Works

Kadane's algorithm scans the array from left to right, keeping track of the maximum sum subarray ending at each position. The key insight is that if the current running sum becomes negative, it's better to start a new subarray from the current position.

Generic Template

Kadane's Algorithm Time: O(n) | Space: O(1)

// Kadane's Algorithm for Maximum Subarray Sum
public int maxSubArray(int[] nums) {
   // Initialize variables
   int maxSoFar = nums[0]; // Maximum sum found so far
   int maxEndingHere = nums[0]; // Maximum sum ending at current position
   
   // Start from the second element
   for (int i = 1; i < nums.length; i++) {
       // Either start a new subarray or extend existing one
       maxEndingHere = Math.max(nums[i], maxEndingHere + nums[i]);
       
       // Update maximum sum found so far
       maxSoFar = Math.max(maxSoFar, maxEndingHere);
   }
   
   return maxSoFar;
}

# Kadane's Algorithm for Maximum Subarray Sum
def max_subarray(nums):
   # Initialize variables
   max_so_far = nums[0]  # Maximum sum found so far
   max_ending_here = nums[0]  # Maximum sum ending at current position
   
   # Start from the second element
   for i in range(1, len(nums)):
       # Either start a new subarray or extend existing one
       max_ending_here = max(nums[i], max_ending_here + nums[i])
       
       # Update maximum sum found so far
       max_so_far = max(max_so_far, max_ending_here)
   
   return max_so_far

// Kadane's Algorithm for Maximum Subarray Sum
function maxSubArray(nums) {
   // Initialize variables
   let maxSoFar = nums[0]; // Maximum sum found so far
   let maxEndingHere = nums[0]; // Maximum sum ending at current position
   
   // Start from the second element
   for (let i = 1; i < nums.length; i++) {
       // Either start a new subarray or extend existing one
       maxEndingHere = Math.max(nums[i], maxEndingHere + nums[i]);
       
       // Update maximum sum found so far
       maxSoFar = Math.max(maxSoFar, maxEndingHere);
   }
   
   return maxSoFar;
}

Variations and Extensions

Circular Maximum Subarray Sum: Find maximum subarray sum in a circular array
Maximum Product Subarray: Find the contiguous subarray that has the largest product
Maximum Subarray Sum After One Deletion: Find maximum subarray sum after removing exactly one element
2D/Matrix Kadane's Algorithm: Extension to find maximum sum submatrix in a 2D array

How to Identify: Consider using Kadane's algorithm when:

You need to find the maximum (or minimum) sum subarray
You're dealing with problems asking for "maximum contiguous..." or "largest sum of contiguous..."
The problem involves finding optimal subarray/substring with additivity property
You need to find the best segment of data according to some criteria
The problem can be solved by determining whether to extend the current segment or start a new one

Boyer-Moore Voting Algorithm O(n)

An efficient algorithm to find the majority element in an array (an element appearing more than n/2 times) with O(n) time complexity and O(1) space complexity.

Speed:

How It Works

The algorithm uses a voting mechanism where we maintain a candidate and a count. We increment the count when we see the same element and decrement when we see a different element. If the count becomes zero, we choose a new candidate. The intuition is that the majority element will survive the "elimination" process.

Generic Template

Boyer-Moore Voting Algorithm Time: O(n) | Space: O(1)

// Boyer-Moore Voting Algorithm for Majority Element
public int majorityElement(int[] nums) {
   int count = 0;
   Integer candidate = null;
   
   // Find candidate for majority element
   for (int num : nums) {
       if (count == 0) {
           candidate = num;
       }
       
       count += (num == candidate) ? 1 : -1;
   }
   
   // Optional: Verify the candidate is a majority element
   // Count occurrences of the candidate
   count = 0;
   for (int num : nums) {
       if (num == candidate) {
           count++;
       }
   }
   
   // Check if the candidate appears more than n/2 times
   if (count > nums.length / 2) {
       return candidate;
   } else {
       throw new IllegalArgumentException("No majority element exists");
   }
}

# Boyer-Moore Voting Algorithm for Majority Element
def majority_element(nums):
   count = 0
   candidate = None
   
   # Find candidate for majority element
   for num in nums:
       if count == 0:
           candidate = num
       
       count += 1 if num == candidate else -1
   
   # Optional: Verify the candidate is a majority element
   # Count occurrences of the candidate
   count = sum(1 for num in nums if num == candidate)
   
   # Check if the candidate appears more than n/2 times
   if count > len(nums) // 2:
       return candidate
   else:
       raise ValueError("No majority element exists")

// Boyer-Moore Voting Algorithm for Majority Element
function majorityElement(nums) {
   let count = 0;
   let candidate = null;
   
   // Find candidate for majority element
   for (const num of nums) {
       if (count === 0) {
           candidate = num;
       }
       
       count += (num === candidate) ? 1 : -1;
   }
   
   // Optional: Verify the candidate is a majority element
   // Count occurrences of the candidate
   count = nums.filter(num => num === candidate).length;
   
   // Check if the candidate appears more than n/2 times
   if (count > nums.length / 2) {
       return candidate;
   } else {
       throw new Error("No majority element exists");
   }
}

Extensions

The algorithm can be extended to find multiple majority elements:

Finding elements that appear more than n/3 times: Use two counters and two candidates (Moore's extended voting algorithm)
Finding elements that appear more than n/k times: Use k-1 counters and candidates

How to Identify: Consider using Boyer-Moore Voting algorithm when:

You need to find the majority element (element appearing more than n/2 times) in an array
The problem asks for O(1) space complexity for finding dominant elements
You need to identify elements with frequency above certain thresholds (n/2, n/3, etc.)
The problem involves finding elements that "dominate" in some sense
You see terms like "majority element," "dominant element," or "element appearing more than n/x times"

Building an ArrayList from Scratch

An ArrayList is a resizable array implementation that combines the random access efficiency of arrays with dynamic sizing capability.

Core Design Principles Dynamic Size

Backing Array: Uses a standard array to store elements
Capacity Management: Tracks both size (number of elements) and capacity (total available slots)
Automatic Resizing: When array becomes full, creates a new larger array (typically double the size)
Average Efficiency: Most operations have O(1) on average time complexity

Size: 4 | Capacity: 8 | Load Factor: 50%

Key Operations and Complexity

Operation	Description	Time Complexity
add(element)	Append element to end	O(1) on average
add(index, element)	Insert at specific position	O(n) worst case
get(index)	Access element by index	O(1)
set(index, element)	Update element at position	O(1)
remove(index)	Delete element by position	O(n) worst case
size()	Get number of elements	O(1)

Design Insight: The key to ArrayList's efficiency is its on average analysis. While resizing is an O(n) operation, it happens infrequently enough that the average cost per operation remains constant.

ArrayList Implementation

Let's implement a basic ArrayList from scratch to understand its internal workings.

public class ArrayList<E>{
    private static final int DEFAULT_CAPACITY = 10;
    private Object[] elements;
    private int size;
    
    // Constructor
    public ArrayList() {
        this.elements = new Object[DEFAULT_CAPACITY];
        this.size = 0;
    }
    
    // Add element to the end (potentially resize)
    public boolean add(E element) {
        ensureCapacity(size + 1);
        elements[size++] = element;
        return true;
    }
    
    // Insert element at specific index
    public void add(int index, E element) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        }
        
        ensureCapacity(size + 1);
        
        // Shift elements to make room
        System.arraycopy(elements, index, elements, index + 1, size - index);
        elements[index] = element;
        size++;
    }
    
    // Ensure the underlying array has enough space
    private void ensureCapacity(int minCapacity) {
        if (minCapacity > elements.length) {
            int newCapacity = Math.max(elements.length * 2, minCapacity);
            Object[] newElements = new Object[newCapacity];
            System.arraycopy(elements, 0, newElements, 0, size);
            elements = newElements;
        }
    }
    
    // Get element at index
    @SuppressWarnings("unchecked")
    public E get(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        }
        return (E) elements[index];
    }
    
    // Update element at index
    public E set(int index, E element) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        }
        
        @SuppressWarnings("unchecked")
        E oldValue = (E) elements[index];
        elements[index] = element;
        return oldValue;
    }
    
    // Remove element at index
    @SuppressWarnings("unchecked")
    public E remove(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        }
        
        E oldValue = (E) elements[index];
        
        // Shift elements to close the gap
        int numMoved = size - index - 1;
        if (numMoved > 0) {
            System.arraycopy(elements, index + 1, elements, index, numMoved);
        }
        
        // Clear the last position and decrement size
        elements[--size] = null;
        return oldValue;
    }
    
    // Get current size
    public int size() {
        return size;
    }
    
    // Check if empty
    public boolean isEmpty() {
        return size == 0;
    }
}

class ArrayList:
    def __init__(self):
        self._DEFAULT_CAPACITY = 10
        self._elements = [None] * self._DEFAULT_CAPACITY
        self._size = 0
    
    # Add element to the end (potentially resize)
    def add(self, element):
        self._ensure_capacity(self._size + 1)
        self._elements[self._size] = element
        self._size += 1
        return True
    
    # Insert element at specific index
    def insert(self, index, element):
        if index < 0 or index > self._size:
            raise IndexError(f"Index: {index}, Size: {self._size}")
        
        self._ensure_capacity(self._size + 1)
        
        # Shift elements to make room
        for i in range(self._size, index, -1):
            self._elements[i] = self._elements[i - 1]
            
        self._elements[index] = element
        self._size += 1
    
    # Ensure the underlying array has enough space
    def _ensure_capacity(self, min_capacity):
        if min_capacity > len(self._elements):
            new_capacity = max(len(self._elements) * 2, min_capacity)
            new_elements = [None] * new_capacity
            
            # Copy elements to new array
            for i in range(self._size):
                new_elements[i] = self._elements[i]
                
            self._elements = new_elements
    
    # Get element at index
    def get(self, index):
        if index < 0 or index >= self._size:
            raise IndexError(f"Index: {index}, Size: {self._size}")
        return self._elements[index]
    
    # Update element at index    
    def set(self, index, element):
        if index < 0 or index >= self._size:
            raise IndexError(f"Index: {index}, Size: {self._size}")
        
        old_value = self._elements[index]
        self._elements[index] = element
        return old_value
    
    # Remove element at index
    def remove(self, index):
        if index < 0 or index >= self._size:
            raise IndexError(f"Index: {index}, Size: {self._size}")
        
        old_value = self._elements[index]
        
        # Shift elements to close the gap
        for i in range(index, self._size - 1):
            self._elements[i] = self._elements[i + 1]
        
        # Clear the last position and decrement size
        self._elements[self._size - 1] = None
        self._size -= 1
        return old_value
    
    # Get current size
    def size(self):
        return self._size
    
    # Check if empty    
    def is_empty(self):
        return self._size == 0
    
    # Python specific methods for list-like behavior
    def __len__(self):
        return self._size
    
    def __getitem__(self, index):
        return self.get(index)
    
    def __setitem__(self, index, value):
        self.set(index, value)

class ArrayList {
  constructor() {
    this._DEFAULT_CAPACITY = 10;
    this._elements = new Array(this._DEFAULT_CAPACITY);
    this._size = 0;
  }
  
  // Add element to the end (potentially resize)
  add(element) {
    this._ensureCapacity(this._size + 1);
    this._elements[this._size++] = element;
    return true;
  }
  
  // Insert element at specific index
  insert(index, element) {
    if (index < 0 || index > this._size) {
      throw new Error(`Index: ${index}, Size: ${this._size}`);
    }
    
    this._ensureCapacity(this._size + 1);
    
    // Shift elements to make room
    for (let i = this._size; i > index; i--) {
      this._elements[i] = this._elements[i - 1];
    }
    
    this._elements[index] = element;
    this._size++;
  }
  
  // Ensure the underlying array has enough space
  _ensureCapacity(minCapacity) {
    if (minCapacity > this._elements.length) {
      const newCapacity = Math.max(this._elements.length * 2, minCapacity);
      const newElements = new Array(newCapacity);
      
      // Copy elements to new array
      for (let i = 0; i < this._size; i++) {
        newElements[i] = this._elements[i];
      }
      
      this._elements = newElements;
    }
  }
  
  // Get element at index
  get(index) {
    if (index < 0 || index >= this._size) {
      throw new Error(`Index: ${index}, Size: ${this._size}`);
    }
    return this._elements[index];
  }
  
  // Update element at index
  set(index, element) {
    if (index < 0 || index >= this._size) {
      throw new Error(`Index: ${index}, Size: ${this._size}`);
    }
    
    const oldValue = this._elements[index];
    this._elements[index] = element;
    return oldValue;
  }
  
  // Remove element at index
  remove(index) {
    if (index < 0 || index >= this._size) {
      throw new Error(`Index: ${index}, Size: ${this._size}`);
    }
    
    const oldValue = this._elements[index];
    
    // Shift elements to close the gap
    for (let i = index; i < this._size - 1; i++) {
      this._elements[i] = this._elements[i + 1];
    }
    
    // Clear the last position and decrement size
    this._elements[--this._size] = undefined;
    return oldValue;
  }
  
  // Get current size
  size() {
    return this._size;
  }
  
  // Check if empty
  isEmpty() {
    return this._size === 0;
  }
}

Key Implementation Aspects

Dynamic Resizing: The ensureCapacity method doubles the array size when needed
Efficient Shifting: Uses system array copy for fast bulk element movement when applicable
Boundary Checks: Includes proper index validation to prevent out-of-bounds access
Null Handling: Explicitly sets removed elements to null to aid garbage collection

Performance Insight: The most expensive operation is resizing, which has O(n) complexity. However, this happens infrequently (logarithmically with respect to the number of operations), leading to on average O(1) performance for appends.

ArrayList Operations Visualization

See how ArrayList operations work internally with this interactive visualization.

Current ArrayList State

ArrayList Info

Size: 4 | Capacity: 8 | Load Factor: 50%

Operations

Result

Animation Speed:

Implementation Note: The key to efficient ArrayList operations is balancing between excessive resizing (wasting memory) and too little resizing (wasting time copying elements). Most implementations double the size when capacity is reached, which provides a good balance.

Arrays

What is an Array?

Key Characteristics

Types of Arrays

1. Static Arrays Fixed Size

2. Dynamic Arrays Resizable

Memory Layout of Arrays

How Arrays Work in Memory

Memory Allocation

Array Operations Complexity

Accessing Elements O(1)

Traversing Arrays O(n)

Common Traversal Patterns

Inserting Elements

Insertion Operations

Deleting Elements

Deletion Operations

Searching in Arrays

Linear Search O(n)

Linear Search Time: O(n) | Space: O(1)

Binary Search O(log n)

Binary Search Time: O(log n) | Space: O(1)

Binary Search Algorithm O(log n)

How Binary Search Works

Implementation

Binary Search Time: O(log n) | Space: O(1)

Time Complexity Analysis

Two Pointer Technique O(n)

Generic Template

Two Pointers (Opposite Directions) Time: O(n) | Space: O(1)

Common Problems

Generic Template

Two Pointers (Same Direction) Time: O(n) | Space: O(1)

Common Problems

Sliding Window Technique O(n)

Generic Template

Fixed Size Sliding Window Time: O(n) | Space: O(1)

Common Problems

Generic Template

Variable Size Sliding Window Time: O(n) | Space: O(1) or O(k)

Common Problems

Prefix Sum Technique O(1) queries after O(n) preprocessing

How It Works

Generic Template

Prefix Sum Precomputation: O(n) | Query: O(1)

Common Problems

Kadane's Algorithm O(n)

How It Works

Generic Template

Kadane's Algorithm Time: O(n) | Space: O(1)

Variations and Extensions

Boyer-Moore Voting Algorithm O(n)

How It Works

Generic Template

Boyer-Moore Voting Algorithm Time: O(n) | Space: O(1)

Extensions

Building an ArrayList from Scratch

Core Design Principles Dynamic Size

Key Operations and Complexity

ArrayList Implementation

Key Implementation Aspects

ArrayList Operations Visualization

Login Required