Arrays & Strings¶

Definition¶

Arrays and Strings Visualization

Big O Complexity¶

Array Time and Space Complexity

When to Use¶

USE WHEN: - Need fast random access by index - Know the size ahead of time (static array) - Data is naturally sequential - Need cache-friendly iteration - Memory efficiency is important - Need to store primitive types efficiently

DON'T USE WHEN: - Frequent insertions/deletions in middle - Size changes frequently and unpredictably - Need fast search without sorting - Need key-value associations

Common Use Cases: - Storing collections of similar items - Implementing other data structures (heap, hash table) - Matrix/grid problems - Sliding window problems - Buffer implementations

Pros and Cons¶

PROS: - O(1) random access - fastest possible - Cache-friendly - contiguous memory - Simple and intuitive - Memory efficient - no pointer overhead - Predictable memory layout - Works well with CPU prefetching

CONS: - Fixed size (static arrays) - Expensive insert/delete (must shift elements) - Wasted space if over-allocated - Resize is expensive O(n) operation - Can't efficiently insert in sorted order

STRING-SPECIFIC: - Immutability provides thread safety (Java/Python) - Immutability means concatenation creates new objects - Use StringBuilder/StringBuffer for many concatenations

Implementation Examples¶

Basic Array Operations¶

// Declaration and initialization
int[] arr = new int[5];                    // [0, 0, 0, 0, 0]
int[] arr2 = {1, 2, 3, 4, 5};             // [1, 2, 3, 4, 5]
int[] arr3 = new int[]{1, 2, 3};          // [1, 2, 3]

// Access - O(1)
int element = arr2[2];  // 3

// Modify - O(1)
arr2[2] = 10;  // [1, 2, 10, 4, 5]

// Length
int length = arr2.length;  // 5

// Iteration
for (int i = 0; i < arr2.length; i++) {
    System.out.println(arr2[i]);
}

// Enhanced for loop
for (int num : arr2) {
    System.out.println(num);
}

// 2D Array
int[][] matrix = new int[3][4];  // 3 rows, 4 columns
int[][] matrix2 = {
    {1, 2, 3},
    {4, 5, 6},
    {7, 8, 9}
};

Dynamic Array (ArrayList)¶

import java.util.ArrayList;
import java.util.List;

// Creation
List<Integer> list = new ArrayList<>();

// Add - O(1) amortized
list.add(10);           // [10]
list.add(20);           // [10, 20]
list.add(1, 15);        // [10, 15, 20] - insert at index 1

// Access - O(1)
int val = list.get(0);  // 10

// Update - O(1)
list.set(0, 5);         // [5, 15, 20]

// Remove - O(n)
list.remove(1);         // [5, 20] - remove at index
list.remove(Integer.valueOf(20));  // [5] - remove by value

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

// Check if contains - O(n)
boolean contains = list.contains(5);  // true

// Convert to array
Integer[] arr = list.toArray(new Integer[0]);

String Operations¶

// Creation
String s1 = "Hello";
String s2 = new String("Hello");
char[] chars = {'H', 'e', 'l', 'l', 'o'};
String s3 = new String(chars);

// Length - O(1) in Java (stored)
int len = s1.length();  // 5

// Access character - O(1)
char c = s1.charAt(0);  // 'H'

// Substring - O(n)
String sub = s1.substring(1, 4);  // "ell"

// Concatenation - O(n + m)
String s4 = s1 + " World";  // "Hello World"

// Compare
boolean equals = s1.equals(s2);           // true
int cmp = s1.compareTo("Hallo");          // positive (e > a)
boolean equalsIgnore = s1.equalsIgnoreCase("HELLO");  // true

// Search
int index = s1.indexOf('l');              // 2 (first occurrence)
int lastIndex = s1.lastIndexOf('l');      // 3
boolean contains = s1.contains("ell");    // true

// Conversion
String upper = s1.toUpperCase();          // "HELLO"
String lower = s1.toLowerCase();          // "hello"
char[] charArray = s1.toCharArray();      // ['H','e','l','l','o']

// Split
String[] parts = "a,b,c".split(",");      // ["a", "b", "c"]

// StringBuilder for efficient concatenation
StringBuilder sb = new StringBuilder();
for (int i = 0; i < 1000; i++) {
    sb.append(i);  // O(1) amortized
}
String result = sb.toString();

Common Patterns & Problems¶

Two Pointers¶

// Reverse array in place
public void reverse(int[] arr) {
    int left = 0, right = arr.length - 1;
    while (left < right) {
        int temp = arr[left];
        arr[left] = arr[right];
        arr[right] = temp;
        left++;
        right--;
    }
}

// Two Sum (sorted array)
public int[] twoSum(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left < right) {
        int sum = nums[left] + nums[right];
        if (sum == target) {
            return new int[]{left, right};
        } else if (sum < target) {
            left++;
        } else {
            right--;
        }
    }
    return new int[]{-1, -1};
}

Sliding Window¶

// Maximum sum subarray of size k
public int maxSumSubarray(int[] arr, int k) {
    int windowSum = 0;
    int maxSum = Integer.MIN_VALUE;

    for (int i = 0; i < arr.length; i++) {
        windowSum += arr[i];

        if (i >= k - 1) {
            maxSum = Math.max(maxSum, windowSum);
            windowSum -= arr[i - k + 1];
        }
    }
    return maxSum;
}

// Longest substring without repeating characters
public int lengthOfLongestSubstring(String s) {
    Map<Character, Integer> map = new HashMap<>();
    int maxLen = 0, left = 0;

    for (int right = 0; right < s.length(); right++) {
        char c = s.charAt(right);
        if (map.containsKey(c)) {
            left = Math.max(left, map.get(c) + 1);
        }
        map.put(c, right);
        maxLen = Math.max(maxLen, right - left + 1);
    }
    return maxLen;
}

Prefix Sum¶

// Range sum query
class NumArray {
    private int[] prefix;

    public NumArray(int[] nums) {
        prefix = new int[nums.length + 1];
        for (int i = 0; i < nums.length; i++) {
            prefix[i + 1] = prefix[i] + nums[i];
        }
    }

    public int sumRange(int left, int right) {
        return prefix[right + 1] - prefix[left];
    }
}

String Problems¶

// Check if anagram
public boolean isAnagram(String s, String t) {
    if (s.length() != t.length()) return false;

    int[] count = new int[26];
    for (int i = 0; i < s.length(); i++) {
        count[s.charAt(i) - 'a']++;
        count[t.charAt(i) - 'a']--;
    }

    for (int c : count) {
        if (c != 0) return false;
    }
    return true;
}

// Longest palindromic substring
public String longestPalindrome(String s) {
    if (s == null || s.length() < 1) return "";
    int start = 0, end = 0;

    for (int i = 0; i < s.length(); i++) {
        int len1 = expandAroundCenter(s, i, i);     // odd length
        int len2 = expandAroundCenter(s, i, i + 1); // even length
        int len = Math.max(len1, len2);

        if (len > end - start) {
            start = i - (len - 1) / 2;
            end = i + len / 2;
        }
    }
    return s.substring(start, end + 1);
}

private int expandAroundCenter(String s, int left, int right) {
    while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
        left--;
        right++;
    }
    return right - left - 1;
}

Tips & Tricks¶

Arrays: - Use Arrays.sort() for sorting - O(n log n) - Use Arrays.binarySearch() for sorted arrays - Use System.arraycopy() for efficient copying - Arrays.fill() to initialize with a value

Strings: - Use StringBuilder for concatenation in loops - String.join() for joining with delimiter - Strings are immutable - each operation creates new - Use char[] for in-place string manipulation

Common Interview Tips: - Consider edge cases: empty, single element, duplicates - Think about in-place vs extra space - Two pointers often optimize O(n^2) to O(n) - Sliding window for subarray/substring problems - Sorting can simplify many problems