Why a global array declaration makes the tests fail?

Viewed 47

I am working on LeetCode problem 438. Find All Anagrams in a String:

Given two strings s and p, return an array of all the start indices of p's anagrams in s. You may return the answer in any order.

s and p consist of lowercase English letters.

My Approach

I store the frequency of each character in an array and use a sliding window.

1. Using a global array declaration

let arr:number[]=[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]; // outside any function
function check(arr1:number[],arr2:number[]):boolean{
    for (let i=0;i<26;i++){
        if (arr1[i]!=arr2[i]){
            return false;
        }
    }
    return true;
}
function findAnagrams(s: string, p: string): number[] {
    let ans:number[]=[],
    lengthP:number=p.length,
    lengthS:number=s.length,
    j:number=0;
    if (lengthP>lengthS){
        return ans;
    }
    let arrP:number[]= [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0];
    for (let chr of p){
        arrP[chr.charCodeAt(0)-97]++;
    }
    for (let i=0;i<lengthP;i++){
        arr[s[i].charCodeAt(0)-97]++;
    }
    if (check(arr,arrP)){
        ans.push(0);
    }
    for (let i=lengthP;i<lengthS;i++){
        arr[s[j].charCodeAt(0)-97]--;
        arr[s[i].charCodeAt(0)-97]++;
        j++;
        if (check(arr,arrP)){
            ans.push(j);
        }
    
    }
    return ans;
};

2. Using a functional scope array declaration

function check(arr1:number[],arr2:number[]):boolean{
    for (let i=0;i<26;i++){
        if (arr1[i]!=arr2[i]){
            return false;
        }
    }
    return true;
}
function findAnagrams(s: string, p: string): number[] {
    let arr:number[]=[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]; // inside function
    let ans:number[]=[],
    lengthP:number=p.length,
    lengthS:number=s.length,
    j:number=0;
    if (lengthP>lengthS){
        return ans;
    }
    let arrP:number[]= [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0];
    for (let chr of p){
        arrP[chr.charCodeAt(0)-97]++;
    }
    for (let i=0;i<lengthP;i++){
        arr[s[i].charCodeAt(0)-97]++;
    }
    if (check(arr,arrP)){
        ans.push(0);
    }
    for (let i=lengthP;i<lengthS;i++){
        arr[s[j].charCodeAt(0)-97]--;
        arr[s[i].charCodeAt(0)-97]++;
        j++;
        if (check(arr,arrP)){
            ans.push(j);
        }
    
    }
    return ans;

};

The problem

The first one is giving the wrong answer on some test cases, but the second one is 100% correct.

Is this really happening because of the way arr is declared?

If Yes, then am I missing something about local and global declaration in Typescript?

1 Answers

The problem with using a global array is that it will persist across multiple calls of findAnagrams. So, while the first call will give a correct result, the second call will not start with a zero-filled arr, but will build on the results of the previous call, which obviously leads to incorrect counts.

This is not related to TypeScript specifically -- it would be the same in plain JavaScript.

You could fix the first version by resetting the values in arr at the start of findAnagrams:

arr.fill(0);

But it is any way better practice to keep such a variable locally scoped.

Related