Arrays & Strings

Arrays are contiguous memory blocks with O(1) random access. Strings in Java are immutable char[] backed objects. Key techniques: two pointers (opposite ends or same direction), sliding window (subarray problems), prefix sums (range queries), sorting + binary search. Time complexities: access O(1), search O(n), insert/delete O(n).

Key Concepts

Deep Dive: Array Operations Complexity

Operation	Array	ArrayList	LinkedList
Access by index	O(1)	O(1)	O(n)
Search	O(n)	O(n)	O(n)
Insert at end	O(1)*	O(1)*	O(1)
Insert at middle	O(n)	O(n)	O(1)**
Delete	O(n)	O(n)	O(1)**

amortized (resize when full) *if you have the node reference

Deep Dive: Two Pointer Technique

Problem: 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[]{};
}

Problem: Remove duplicates from sorted array (in-place)

public int removeDuplicates(int[] nums) {
    int slow = 0;
    for (int fast = 1; fast < nums.length; fast++) {
        if (nums[fast] != nums[slow]) {
            nums[++slow] = nums[fast];
        }
    }
    return slow + 1;
}

Deep Dive: Prefix Sum

Range sum queries in O(1) after O(n) preprocessing:

int[] prefix = new int[nums.length + 1];
for (int i = 0; i < nums.length; i++) {
    prefix[i + 1] = prefix[i] + nums[i];
}
// Sum of nums[left..right] = prefix[right+1] - prefix[left]

Deep Dive: String Problems

Reverse a string in-place:

public void reverseString(char[] s) {
    int l = 0, r = s.length - 1;
    while (l < r) {
        char tmp = s[l]; s[l] = s[r]; s[r] = tmp;
        l++; r--;
    }
}

Check palindrome:

public boolean isPalindrome(String s) {
    int l = 0, r = s.length() - 1;
    while (l < r) {
        while (l < r && !Character.isLetterOrDigit(s.charAt(l))) l++;
        while (l < r && !Character.isLetterOrDigit(s.charAt(r))) r--;
        if (Character.toLowerCase(s.charAt(l)) != Character.toLowerCase(s.charAt(r)))
            return false;
        l++; r--;
    }
    return true;
}

Anagram check:

public boolean isAnagram(String s, String t) {
    int[] count = new int[26];
    for (char c : s.toCharArray()) count[c - 'a']++;
    for (char c : t.toCharArray()) count[c - 'a']--;
    for (int c : count) if (c != 0) return false;
    return true;
}

Common Interview Questions

• Two Sum (unsorted and sorted)
• Best Time to Buy and Sell Stock
• Container With Most Water
• Product of Array Except Self
• Longest Substring Without Repeating Characters
• Valid Palindrome
• Group Anagrams
• Merge Intervals