Frequency Same

Problem

Write a function called same that accepts two arrays. The function should return true if every value in the first array has its corresponding value squared in the second array. The frequency of values must be the same: if 2 appears twice in the first array, 4 must appear twice in the second.

Example 1:

Input: arr1 = [1,2,3], arr2 = [4,1,9] Output: true (1->1, 2->4, 3->9, order does not matter)

Example 2:

Input: arr1 = [1,2,3], arr2 = [1,9] Output: false (different lengths)

Example 3:

Input: arr1 = [1,2,1], arr2 = [4,4,1] Output: false (frequencies do not match: 1 appears twice but 1 appears once in arr2)

Solution

This is the classic frequency counter pattern. The naive approach nests a loop with indexOf, which is O(n^2). Instead, count how many times each value appears in each array with two objects, then compare: for every key in the first counter, its square must exist in the second counter with the same count.

function same(arr1: number[], arr2: number[]): boolean {
  if (arr1.length !== arr2.length) {
    return false;
  }

  let frequency1: { [key: string]: number } = {};
  let frequency2: { [key: string]: number } = {};

  for (let key of arr1) {
    frequency1[key] = (frequency1[key] || 0) + 1;
  }

  for (let key of arr2) {
    frequency2[key] = (frequency2[key] || 0) + 1;
  }

  for (let key in frequency1) {
    if (!(Number(key) ** 2 in frequency2)) {
      return false;
    }

    if (frequency2[Number(key) ** 2] !== frequency1[key]) {
      return false;
    }
  }
  return true;
}

Complexity Analysis

• Three separate loops instead of nested ones: that is the whole point of the pattern

Notes

• Early exit on different lengths saves building the counters at all.
• Object keys are strings, so the numeric key needs Number(key) before squaring.
• The frequency counter pattern shows up everywhere: anagrams, character counts, comparing multisets.