DSA Fundamentals: Arrays & Strings II - Advanced Patterns & LeetCode Practice

Arrays and strings keep showing up in increasingly tricky forms in coding interviews. Beyond basic traversal and hashing, many problems are solved using clever patterns like majority voting, frequency-based sorting, bitwise XOR, and in-place marking to hit the O(n) time and O(1) / O(k) space targets.

This guide builds on the first Arrays & Strings post and focuses on advanced patterns through five representative LeetCode problems.

Advanced Arrays & Strings Patterns Overview

Before diving into problems, here are the key patterns we'll use:

• Majority Voting (Boyer–Moore): Track a candidate and a counter to find a majority element in O(n) time and O(1) space.
• Frequency Hashing: Count occurrences with a hash map and then:
  • Use them for decisions (first unique character)
  • Sort by frequency (sort characters by frequency)
• XOR Trick: Use properties of XOR to cancel out duplicates and isolate a missing value.
• In-Place Index Marking: Use the input array as a visited/marked structure by flipping signs.

We’ll now see how these patterns apply in real interview-style problems.

1. Majority Element (LeetCode 169) – Boyer–Moore Voting Algorithm

Problem:
Given an array nums of size n, return the majority element (the element that appears more than ⌊n / 2⌋ times). You may assume that the majority element always exists in the array.

Goal: O(n) time, O(1) extra space.

Approach: Boyer–Moore Majority Vote

Intuition:

• Keep a candidate and a count.
• When count is 0, set the current number as the new candidate.
• If the current number equals the candidate → increment count.
• Otherwise → decrement count.

Because the majority element appears more than half the time, all other elements together cannot fully cancel it out.

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        candidate = None
        count = 0

        for num in nums:
            # If count is zero, choose new candidate
            if count == 0:
                candidate = num

            # Update count based on current number
            if num == candidate:
                count += 1
            else:
                count -= 1

        return candidate

Time Complexity: O(n) – single pass through array
Space Complexity: O(1) – constant extra variables

Why It Works

Think of pairing each occurrence of the majority element with a different element:

• Every time we see a non-majority element, it can “cancel” one count of the majority.
• Since the majority appears more than n/2 times, after all cancellations, the majority element is guaranteed to remain as the final candidate.

This algorithm is a great example of how counting + greedy cancellation can replace hash maps for specific problems.

---

2. First Unique Character in a String (LeetCode 387)

Problem:
Given a string s, return the index of the first non-repeating character. If it does not exist, return -1.

Approach: Two Passes with Hash Map

Steps:

1. First pass: Build a frequency map of characters.
2. Second pass: Iterate again using enumerate; the first character with frequency 1 is the answer.

You can use collections.Counter, but here we’ll use a simple dictionary for clarity.

class Solution:
    def firstUniqChar(self, s: str) -> int:
        freq = {}

        # First pass: count frequencies
        for ch in s:
            freq[ch] = freq.get(ch, 0) + 1

        # Second pass: find first index with frequency 1
        for i, ch in enumerate(s):
            if freq[ch] == 1:
                return i

        return -1

Time Complexity: O(n) – two passes over string
Space Complexity: O(1) – at most 26 lowercase letters (or O(k) for general char set)

Why Two Passes?

• First pass: collect enough information (frequency).
• Second pass: enforce the “first” condition.
• This pattern – count first, then decide – is extremely common in string problems.

---

3. Sort Characters by Frequency (LeetCode 451)

Problem:
Given a string s, sort it in decreasing order based on the frequency of the characters.

Approach: Frequency Map + Sorting + Rebuild String

Steps:

1. Build a frequency map {char: count}.
2. Sort the items by frequency in descending order.
3. For each (char, count) pair in sorted order, append char repeated count times to the result.

class Solution:
    def frequencySort(self, s: str) -> str:
        # Frequency map
        freq = {}
        for ch in s:
            freq[ch] = freq.get(ch, 0) + 1

        # Sort characters by frequency (descending)
        # freq.items() -> (char, count)
        sorted_chars = sorted(freq.items(), key=lambda x: x[1], reverse=True)

        # Build result string
        res = []
        for ch, count in sorted_chars:
            # Append character 'count' times
            res.append(ch * count)

        return "".join(res)

Time Complexity: O(n log k)

• n = length of string
• k = number of distinct characters
• Sorting k entries by frequency costs O(k log k) ≤ O(n log n).

Space Complexity: O(n) – result string plus frequency map

Variations and Optimizations

• For small character sets (e.g., only lowercase letters), k is bounded, so sorting is effectively O(1) overhead.
• For larger universes (e.g., full Unicode), bucket sort by frequency can give O(n) time:
  • Create buckets where index = frequency.
  • Place characters in appropriate bucket.
  • Iterate buckets from high to low to build result.

This pattern (frequency + sorting) is broadly useful for “top-k” and “group by frequency” tasks.

---

4. Missing Number (LeetCode 268) – XOR Trick

Problem:
Given an array nums containing n distinct numbers in the range [0, n], return the one number that is missing from the array.

Approach 1: XOR Over Indices and Values

Key XOR properties:

• x ^ x = 0
• x ^ 0 = x
• XOR is associative and commutative

If we XOR all indices and all values together, everything that appears twice cancels out, and we’re left with the missing number.

Steps:

1. Initialize res as n (the length of the array).
2. For each index i from 0 to n-1:
   • res = res ^ i ^ nums[i]
3. After the loop, res holds the missing number.

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        n = len(nums)
        res = n  # Start with n because indices go from 0 to n-1

        for i in range(n):
            # XOR with index and value
            res ^= i
            res ^= nums[i]

        return res

Time Complexity: O(n) – single pass
Space Complexity: O(1) – constant extra space

Why It Works

• Full set is {0, 1, 2, ..., n}.
• nums contains all except one missing number.
• XOR all of {0..n} and XOR all of nums:
  • Pairwise equal values cancel to 0.
  • Only the missing value remains.

This is a classic example of using bitwise operations to avoid extra memory (like a boolean array or hash set).

Approach 2: Sum Formula (Alternative)

You may also see:

total = n * (n + 1) // 2
return total - sum(nums)

But this can overflow in some languages and uses addition instead of XOR. The XOR trick is more “bitwise DSA” flavored and interview-friendly.

---

5. Find All Numbers Disappeared in an Array (LeetCode 448)

Problem:
Given an array nums of length n where each element is in the range [1, n], some elements appear twice and others appear once. Return all the integers in the range [1, n] that do not appear in nums.

Goal: O(n) time and O(1) extra space (excluding the output array).

Approach: In-Place Index Marking (Sign Flipping)

Key idea:

• Each value v in nums is between 1 and n.
• We can treat index v - 1 as a “marker position”.
• For each number, mark its corresponding position as negative.
• After processing all numbers:
  • Any index i that is still positive means value i + 1 never appeared.

Steps:

1. Iterate through nums:
   • index = abs(nums[i]) - 1
   • If nums[index] > 0, set nums[index] = -nums[index] (mark as seen).
2. Iterate again from 0 to n-1:
   • If nums[i] > 0, then i + 1 is missing.

class Solution:
    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
        n = len(nums)

        # First pass: mark seen numbers by flipping sign
        for i in range(n):
            index = abs(nums[i]) - 1  # Convert value to index
            if nums[index] > 0:
                nums[index] = -nums[index]

        # Second pass: positive indices correspond to missing numbers
        res = []
        for i in range(n):
            if nums[i] > 0:
                res.append(i + 1)  # Convert index back to value

        return res

Time Complexity: O(n) – two linear passes
Space Complexity: O(1) extra – we modify nums in-place

Why It Works

• Each number v in [1, n] maps to unique index v - 1.
• Flipping a value at that index to negative is a “visited” flag.
• If an index’s value never got flipped (stays positive), its corresponding number was never seen in the array.
• This is an example of using the input array as implicit state, a common trick when values are tightly bounded.

Important Details

• Use abs(nums[i]) because we might have already negated some numbers; we only care about their original absolute values.
• Only flip sign when nums[index] > 0 to avoid flipping twice (back to positive).

---

Core Patterns from Today’s Problems

1. Majority Voting (Boyer–Moore)

• When to use: There is guaranteed to be a majority element (> n/2 occurrences).
• Key idea: Maintain a candidate and a counter; cancel out non-majority elements.
• Example: Majority Element (169).

def majorityElement(nums):
    candidate, count = None, 0
    for num in nums:
        if count == 0:
            candidate = num
        count += 1 if num == candidate else -1
    return candidate

2. Frequency Hashing

• When to use: Need counts of elements/characters.
• Key idea: First pass to count, second pass to decide or build result.
• Examples:
  • First Unique Character (387)
  • Sort Characters by Frequency (451)

def firstUniqChar(s):
    freq = {}
    for ch in s:
        freq[ch] = freq.get(ch, 0) + 1
    for i, ch in enumerate(s):
        if freq[ch] == 1:
            return i
    return -1

3. XOR-Based Missing Value Detection

• When to use: Values are in a known range, and exactly one is missing.
• Key idea: XOR of all indices and values cancels duplicates, leaving only the missing one.
• Example: Missing Number (268).

def missingNumber(nums):
    n = len(nums)
    res = n
    for i in range(n):
        res ^= i
        res ^= nums[i]
    return res

4. In-Place Index Marking

• When to use:
  • Values limited to [1, n]
  • Need O(1) extra space
  • Need to mark presence/absence
• Key idea: Use input array as visited/marked flags by flipping signs or adding offsets.
• Example: Find All Numbers Disappeared (448).

def findDisappearedNumbers(nums):
    n = len(nums)
    for i in range(n):
        index = abs(nums[i]) - 1
        if nums[index] > 0:
            nums[index] = -nums[index]
    res = []
    for i in range(n):
        if nums[i] > 0:
            res.append(i + 1)
    return res

---

Common Pitfalls and How to Avoid Them

1. Forgetting Absolute Value in In-Place Marking

# Wrong: might use already-negated value as index
index = nums[i] - 1  # If nums[i] is negative, index is wrong

# Correct:
index = abs(nums[i]) - 1

2. Off-by-One Errors with Ranges

# Missing Number: indices go 0..n-1, values go 0..n
res = n  # Include 'n' in XOR space
for i in range(n):  # i in [0, n-1]
    res ^= i
    res ^= nums[i]

3. Misusing Hash Maps for Majority Element

# Valid but not optimal (O(n) space)
from collections import Counter
def majorityElement(nums):
    counts = Counter(nums)
    return max(counts, key=counts.get)

# Better: Boyer–Moore, O(1) space

4. Inefficient String Building

# Slower: repeated concatenation in loop
res = ""
for ch, count in sorted_chars:
    res += ch * count

# Better: build list, then join once
parts = []
for ch, count in sorted_chars:
    parts.append(ch * count)
res = "".join(parts)

---

Conclusion

In this advanced Arrays & Strings session, you’ve practiced several powerful patterns:

Core Concepts Reinforced:

• Majority Voting (Boyer–Moore) for O(1)-space majority detection.
• Frequency Hashing to drive decisions and sorting.
• Bitwise XOR for missing-element isolation.
• In-Place Index Marking to track presence without extra memory.

Problem-Solving Strategies:

• Look for guarantees in the problem (e.g., majority element exists) to avoid over-engineering.
• When the value range is constrained, consider index-based tricks (sign flipping, offsetting).
• Use two-pass frequency patterns for “first unique” or “frequency-based sorting” problems.
• Prefer XOR or math formulas over extra memory when applicable.

Next Steps:

• Apply these patterns to related problems:
  • Top K Frequent Elements (frequency + heap/bucket sort)
  • Single Number I/II/III (XOR variations)
  • Find All Duplicates in an Array (in-place marking)
• Continue combining these techniques with other paradigms like two pointers and sliding window.

Mastering these advanced patterns will make many array and string problems feel much more mechanical. Once you recognize which pattern fits, implementation becomes straightforward and you can focus on clean, bug-free code.

---

Practice Problems for Mastery:

• 169. Majority Element
• 229. Majority Element II
• 387. First Unique Character in a String
• 451. Sort Characters by Frequency
• 268. Missing Number
• 136. Single Number
• 137. Single Number II
• 260. Single Number III
• 448. Find All Numbers Disappeared in an Array
• 442. Find All Duplicates in an Array

References:

• NeetCode - Arrays & Hashing
• LeetCode Discussion – Majority Vote Algorithm
• LeetCode Patterns
• Grokking Algorithms by Aditya Bhargava

This guide builds on the core concepts from the first Arrays & Strings post and focuses on higher-level patterns that frequently appear in interviews and real-world systems.