Arrays and Strings Problems

# CHAPTER 3

Arrays and Strings Problems #

1. Chapter Introduction #

2. Arrays in Memory #

• Accessing an element via index arr[i]: O(1) Time.

• Searching for an element: O(N) Time.

• Inserting/Deleting at the end: O(1) Time.

• Inserting/Deleting at the beginning: O(N) Time (Because every subsequent element must be physically shifted over by one slot in memory).

3. Pattern 1: Array Traversal & Frequency Counting #

*LeetCode Example:* Majority Element (Find the element that appears > N/2 times). *Approach:* Use a Hash Map to count frequencies.

# Python implementation
def majorityElement(nums):
    countMap = {}
    for num in nums:
        countMap[num] = countMap.get(num, 0) + 1
        if countMap[num] > len(nums) // 2:
            return num
# Time: O(N), Space: O(N)

// Java implementation
public int majorityElement(int[] nums) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int num : nums) {
        map.put(num, map.getOrDefault(num, 0) + 1);
        if (map.get(num) > nums.length / 2) return num;
    }
    return -1;
}

4. Pattern 2: The Prefix Sum Array #

Now, the sum of any subarray from L to R can be calculated in O(1) Time using the formula: Sum(L, R) = prefix[R] - prefix[L - 1]

def buildPrefixSum(nums):
    prefix = [0] * len(nums)
    prefix[0] = nums[0]
    for i in range(1, len(nums)):
        prefix[i] = prefix[i-1] + nums[i]
    return prefix

5. String Manipulation #

*Interview Rule:* If you need to build a string dynamically inside a loop, NEVER use string concatenation (+=).

• In Java: Use StringBuilder.

• In Python: Append characters to a List, then use "".join(list).

# Python: Efficient String Building
def buildString(chars):
    res = []
    for c in chars:
        res.append(c) # O(1) List append
    return "".join(res) # O(N) Join

6. Pattern 3: Palindrome Checking #

// JavaScript implementation
function isPalindrome(s) {
    let left = 0;
    let right = s.length - 1;
    
    while (left < right) {
        if (s[left] !== s[right]) {
            return false;
        }
        left++;
        right--;
    }
    return true;
}
// Time: O(N), Space: O(1)

7. Real-World Scenario: The Subarray Sum #

8. Mini Project: Build an Anagram Checker #

9. Common Mistakes #

• Off-By-One Errors: In 0-indexed languages, looping to i <= len(arr) will cause an "Index Out of Bounds" error. Always use i < len(arr).

• Modifying an Array while iterating over it: Trying to arr.remove(element) inside a for loop will shift all indices and cause massive bugs. Traverse backwards or use a new array.

10. Best Practices #

• Edge Cases First: Start every array problem by checking: if not nums or len(nums) == 0: return 0. Interviewers love candidates who handle edge cases defensively before writing core logic.

11. Exercises #

1. 1. Write a function to reverse an array in-place (O(1) extra space).

1. 2. Trace the Prefix Sum array for the input [2, 4, 6, 8].

12. MCQs #

14. Interview Questions #

• Q: "Given an array nums, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i]. You must write an algorithm that runs in O(n) time and without using the division operation." (LeetCode 238).

15. FAQs #

• Q: Are arrays and lists the same thing?

16. Summary #

17. Next Chapter Recommendation #