Arrays

An array is a contiguous collection of elements stored in memory. Think of it as a row of boxes, each holding one value.

Memory Layout

Array arr = [10, 20, 30, 40, 50]

Memory Address:  1000  1004  1008  1012  1016
                +-----+-----+-----+-----+-----+
                |  10 |  20 |  30 |  40 |  50 |
                +-----+-----+-----+-----+-----+
Index:            0     1     2     3     4

Key Properties

1. Fixed Size: Once created, size cannot change (in Java)
2. Zero-indexed: First element is at index 0
3. Contiguous Memory: Elements are stored next to each other
4. Random Access: Can access any element in O(1) time

Why Arrays Matter

Arrays are the foundation of almost every data structure:

• Strings are arrays of characters
• Stacks can be implemented with arrays
• Heaps are stored as arrays
• Hash Maps use arrays internally

Java Array Declaration

// Declaration and initialization
int[] nums = new int[5];           // Array of 5 zeros
int[] nums = {1, 2, 3, 4, 5};     // Array with values
int[] nums = new int[]{1, 2, 3};   // Alternative syntax

// Accessing elements
int first = nums[0];   // 1
int third = nums[2];   // 3

// Modifying elements
nums[1] = 10;          // Array is now [1, 10, 3, 4, 5]

// Array length
int len = nums.length; // 5

Accessing Elements

// Access by index - O(1)
int value = arr[index];

// Why O(1)?
// Address = base_address + index × element_size
// arr[3] = 1000 + 3 × 4 = 1012 (for int array)

Traversal

// Forward traversal - O(n)
for (int i = 0; i < arr.length; i++) {
    System.out.println(arr[i]);
}

// Enhanced for loop - O(n)
for (int num : arr) {
    System.out.println(num);
}

// Backward traversal - O(n)
for (int i = arr.length - 1; i >= 0; i--) {
    System.out.println(arr[i]);
}

Insertion

// Insert at end - O(1) if space available
// Insert at beginning - O(n) - must shift all elements
// Insert at middle - O(n) - must shift half elements

// Example: Insert 25 at index 2
// Before: [10, 20, 30, 40, 50]
// After:  [10, 20, 25, 30, 40, 50]
//          Shift elements right

Deletion

// Delete from end - O(1)
// Delete from beginning - O(n) - must shift all elements
// Delete from middle - O(n) - must shift elements

// Example: Delete element at index 2
// Before: [10, 20, 30, 40, 50]
// After:  [10, 20, 40, 50]
//          Shift elements left

Search

// Linear Search - O(n)
for (int i = 0; i < arr.length; i++) {
    if (arr[i] == target) return i;
}
return -1;

// Binary Search (sorted array) - O(log n)
int low = 0, high = arr.length - 1;
while (low <= high) {
    int mid = low + (high - low) / 2;
    if (arr[mid] == target) return mid;
    else if (arr[mid] < target) low = mid + 1;
    else high = mid - 1;
}
return -1;

Complexity Summary

Operation	Time	Space
Access	O(1)	O(1)
Search (unsorted)	O(n)	O(1)
Search (sorted)	O(log n)	O(1)
Insert at end	O(1)	O(1)
Insert at beginning	O(n)	O(n)
Delete at end	O(1)	O(1)
Delete at beginning	O(n)	O(n)

Pattern 1: Two Pointers

Use when you need to compare elements from different positions.

// Check if array is palindrome
boolean isPalindrome(int[] arr) {
    int left = 0, right = arr.length - 1;
    while (left < right) {
        if (arr[left] != arr[right]) return false;
        left++;
        right--;
    }
    return true;
}

Pattern 2: Sliding Window

Use when you need to find subarray with certain properties.

// Find max sum of k consecutive elements
int maxSum(int[] arr, int k) {
    int windowSum = 0;
    for (int i = 0; i < k; i++) {
        windowSum += arr[i];
    }
    int maxSum = windowSum;
    for (int i = k; i < arr.length; i++) {
        windowSum += arr[i] - arr[i - k];
        maxSum = Math.max(maxSum, windowSum);
    }
    return maxSum;
}

Pattern 3: Prefix Sum

Use when you need to answer range sum queries.

// Build prefix sum array
int[] prefix = new int[n + 1];
for (int i = 0; i < n; i++) {
    prefix[i + 1] = prefix[i] + arr[i];
}

// Query sum from index i to j
int rangeSum = prefix[j + 1] - prefix[i];

Pattern 4: Sorting First

Use when order doesn't matter.

// Find pair with given sum
Arrays.sort(arr);
int left = 0, right = arr.length - 1;
while (left < right) {
    int sum = arr[left] + arr[right];
    if (sum == target) return true;
    else if (sum < target) left++;
    else right--;
}

Pattern 5: HashMap

Use when you need fast lookup.

// Find two numbers that add to target
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < arr.length; i++) {
    int complement = target - arr[i];
    if (map.containsKey(complement)) {
        return new int[] {map.get(complement), i};
    }
    map.put(arr[i], i);
}

Common Edge Cases

1. Empty Array

int[] arr = {};
arr.length == 0;  // true
// Accessing arr[0] throws ArrayIndexOutOfBoundsException

2. Single Element

int[] arr = {5};
// Any two-pointer technique needs special handling

3. Two Elements

int[] arr = {1, 2};
// Minimum case for many algorithms

4. All Same Elements

int[] arr = {5, 5, 5, 5, 5};
// May cause issues with distinctness requirements

5. Negative Numbers

int[] arr = {-3, -1, -4, -1, -5};
// Affects comparison logic

6. Integer Overflow

int[] arr = {Integer.MAX_VALUE, 1};
// Sum may overflow

7. Sorted vs Unsorted

int[] sorted = {1, 2, 3, 4, 5};
int[] unsorted = {3, 1, 4, 1, 5};
// Different approaches may be needed

How to Handle Edge Cases

Always check before processing:

public int solve(int[] arr) {
    // Handle edge cases first
    if (arr == null || arr.length == 0) {
        return 0; // or throw exception
    }
    if (arr.length == 1) {
        return arr[0]; // or special handling
    }
    
    // Main logic here
    // ...
}

Interview Checklist

Before coding, ask yourself:

1. Can the array be empty?
2. Can it have negative numbers?
3. Can it have duplicate values?
4. Is it sorted?
5. What should I return if no solution exists?
6. Can the result overflow?

Arrays Utility Class

import java.util.Arrays;

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

// Sorting
Arrays.sort(arr);              // [1, 2, 5, 8, 9]

// Searching (binary search, array must be sorted)
int index = Arrays.binarySearch(arr, 5);  // 2

// Filling
Arrays.fill(arr, 0);           // [0, 0, 0, 0, 0]

// Copying
int[] copy = Arrays.copyOf(arr, 3);      // [0, 0, 0]
int[] copy2 = Arrays.copyOfRange(arr, 1, 3); // [0, 0]

// Comparing
boolean equal = Arrays.equals(arr, copy); // false

// String representation
String str = Arrays.toString(arr);       // "[0, 0, 0, 0, 0]"

// 2D array
int[][] grid = {{1, 2}, {3, 4}};
System.out.println(Arrays.deepToString(grid)); // "[[1, 2], [3, 4]]"

ArrayList (Dynamic Array)

import java.util.ArrayList;

ArrayList<Integer> list = new ArrayList<>();

// Adding elements
list.add(1);           // [1]
list.add(2);           // [1, 2]
list.add(0, 3);        // [3, 1, 2] - insert at index 0

// Accessing
int val = list.get(0); // 3

// Modifying
list.set(0, 10);       // [10, 1, 2]

// Removing
list.remove(0);        // [1, 2] - remove by index
list.remove(Integer.valueOf(1)); // [2] - remove by value

// Size
int size = list.size(); // 2

// Searching
boolean has = list.contains(2); // true
int idx = list.indexOf(2);      // 0

// Converting
int[] arr = list.stream().mapToInt(i -> i).toArray();

Common Mistakes with Java Arrays

1. NullPointerException

int[] arr = null;
// arr.length -> NullPointerException
// Always check for null first

2. ArrayIndexOutOfBoundsException

int[] arr = {1, 2, 3};
// arr[3] -> ArrayIndexOutOfBoundsException
// Valid indices: 0, 1, 2

3. Comparing Arrays with ==

int[] a = {1, 2, 3};
int[] b = {1, 2, 3};
a == b;      // false (compares references)
a.equals(b); // false (same as ==)
Arrays.equals(a, b); // true (compares contents)