From Maps to Memory: Optimizing the “Valid Anagram” Problem in JavaScript

The Valid Anagram problem is a classic interview challenge that tests your ability to manage data frequency. While there are many ways to solve it, the journey from using a flexible Map to a high-performance Int32Array reveals a lot about how JavaScript works under the hood.

1. The Foundation: Using a JavaScript Map

The most intuitive way to track character counts is with a Map. It allows for any key type and provides a clean API for getting and setting values.

Here is the implementation using the logic we developed during our session:

function isAnagram(s, t) {
    if (s.length !== t.length) return false;

    const charCount = {}; // Or a Map() for Unicode support

    // Step 1: Map out the first string
    for (let char of s) {
        charCount[char] = (charCount[char] || 0) + 1;
    }

    // Step 2: Walk through the second string
    for (let char of t) {
        if (!charCount[char]) 
            // If the char doesn't exist OR count is already 0, 
            // string 't' has an extra character. Return immediately.
            return false;
        }
        charCount[char]--;
    }

    return true;
}

Why this works:

Readability: The logic of “Add for S, Subtract for T” is very clear.
Flexibility: This solution works for any character set (Unicode, Symbols, Emojis).

2. The Shift: Why Optimize?

While the Map solution is $O(n)$, it carries architectural overhead. A Map is an object where keys are hashed to find memory addresses. For a simple set of 26 lowercase letters, this is like using a massive filing cabinet to store 26 pieces of paper.

3. The Peak: The Fixed Array Approach

If we know the input is limited to lowercase English letters, we can use a Fixed Array. By using the ASCII value of characters (e.g., ‘a’ is 97), we can map characters directly to array indices.

The Evolution: Int32Array

By using Int32Array(26), we tell the computer to reserve a contiguous block of memory for 26 integers. This avoids the “hashing” step and makes lookups incredibly fast.

var isAnagramOptimized = function(s, t) {
    if (s.length !== t.length) return false;

    // A fixed block of memory for 26 letters
    const counter = new Int32Array(26);

    for (let i = 0; i < s.length; i++) {
        // Normalize ASCII values to indices 0-25
        counter[s.charCodeAt(i) - 97]++;
        counter[t.charCodeAt(i) - 97]--;
    }

    // If every 'deposit' from S was 'withdrawn' by T, all indices are 0
    return counter.every(count => count === 0);
};

Summary of Optimization

Feature	Map Solution	Int32Array Solution
Time	$O(n)$	$O(n)$ (but faster constant time)
Space	$O(k)$	$O(1)$ (fixed 26 slots)
Best For	Global Unicode/Symbols	Limited Char Sets (a-z)

techiehub.in