Frequencies of Limited Range Array Elements

TCS NQT Coding Easy Go Ad-Free - ₹20/mo

Given an array A[] of N positive integers which can contain integers from 1 to P where elements can be repeated or absent, count the frequency of all elements from 1 to N.

Note: Elements greater than N can be ignored, and you should modify the array in-place.

Examples:

Input: N = 5, arr = [2,3,2,3,5], P = 5

Output: [0,2,2,0,1]

Explanation: 1 occurs 0 times, 2 occurs 2 times, 3 occurs 2 times, 4 occurs 0 times, 5 occurs 1 time.

Input: N = 4, arr = [3,3,3,3], P = 3

Output: [0,0,4,0]

Explanation: 1 occurs 0 times, 2 occurs 0 times, 3 occurs 4 times, 4 occurs 0 times.

Input: N = 6, arr = [1,4,4,6,6,6], P = 6

Output: [1,0,0,2,0,3]

Explanation: 1 occurs 1 time, 2 occurs 0 times, 3 occurs 0 times, 4 occurs 2 times, 5 occurs 0 times, 6 occurs 3 times.

Constraints

1 ≤ N ≤ 10⁵
1 ≤ P ≤ 4×10⁴
1 ≤ A[i] ≤ P

Editorial

Intuition:

We need to count frequencies of numbers from 1 to N in an array containing values up to P. By converting values to 0-based (subtract 1), we can use array indices to store counts without extra space. A base value (greater than the maximum possible value after conversion) allows us to store both the original value and the count in the same integer via modular arithmetic.

Approach:

Convert all elements to 0-based by subtracting 1.
Let base = P + 1 (ensuring base > any value after conversion).
For each index i, retrieve the original converted value via arr[i] % base. If this value is less than N, add base to arr[value].
After processing, divide each element by base to obtain the frequency.

class Solution {
public:
    void countFrequencies(int N, vector &arr, int P) {
        long long base = P + 1LL;
        vector<long long> temp(N);
        for (int i = 0; i < N; i++) {
            temp[i] = arr[i] - 1;
        }
        for (int i = 0; i < N; i++) {
            long long x = temp[i] % base;
            if (x < N) {
                temp[x] += base;
            }
        }
        for (int i = 0; i < N; i++) {
            arr[i] = temp[i] / base;
        }
    }
};
class Solution {
    public void countFrequencies(int N, int[] arr, int P) {
        long base = P + 1L;
        long[] temp = new long[N];
        for (int i = 0; i < N; i++) {
            temp[i] = arr[i] - 1;
        }
        for (int i = 0; i < N; i++) {
            long x = temp[i] % base;
            if (x < N) {
                temp[(int) x] += base;
            }
        }
        for (int i = 0; i < N; i++) {
            arr[i] = (int) (temp[i] / base);
        }
    }
}
class Solution:
    def count_frequencies(self, N, arr, P):
        base = P + 1
        for i in range(N):
            arr[i] -= 1
        for i in range(N):
            x = arr[i] % base
            if x < N:
                arr[x] += base
        for i in range(N):
            arr[i] //= base
class Solution {
    countFrequencies(N, arr, P) {
        let base = P + 1;
        for (let i = 0; i < N; i++) {
            arr[i]--;
        }
        for (let i = 0; i < N; i++) {
            let x = arr[i] % base;
            if (x < N) {
                arr[x] += base;
            }
        }
        for (let i = 0; i < N; i++) {
            arr[i] = Math.floor(arr[i] / base);
        }
    }
}

Complexity Analysis:

Time Complexity: O(N), we traverse the array three times independently.

Space Complexity: O(N) in C++/Java due to temporary 64-bit array; O(1) in Python/JavaScript as they handle big integers natively.

Notes

Your notes are automatically saved in your browser's local storage and will persist across sessions on this device.

Problem Categories