Code Implementation

class Solution:
    def countSalaryCategories(self, salaries):
        low = mid = high = 0
        for s in salaries:
            if s < 40000:
                low += 1
            elif 40000 <= s < 60000:
                mid += 1
            else:
                high += 1
        return [low, mid, high]
      

class Solution {
public:
    vector<int> countSalaryCategories(vector<int>& salaries) {
        int low = 0, mid = 0, high = 0;
        for (int s : salaries) {
            if (s < 40000) low++;
            else if (s < 60000) mid++;
            else high++;
        }
        return {low, mid, high};
    }
};
      

class Solution {
    public int[] countSalaryCategories(int[] salaries) {
        int low = 0, mid = 0, high = 0;
        for (int s : salaries) {
            if (s < 40000) low++;
            else if (s < 60000) mid++;
            else high++;
        }
        return new int[]{low, mid, high};
    }
}
      

var countSalaryCategories = function(salaries) {
    let low = 0, mid = 0, high = 0;
    for (let s of salaries) {
        if (s < 40000) low++;
        else if (s < 60000) mid++;
        else high++;
    }
    return [low, mid, high];
};
      

Problem Description

You are given an array of integers called salaries, where each element represents the annual salary of an employee. Your task is to count how many employees fall into each of the following salary categories:

• Low salary: Less than 40,000
• Middle salary: 40,000 (inclusive) up to but not including 60,000
• High salary: 60,000 or more

Return an array (or list) with three elements: the number of employees in the low, middle, and high salary categories, respectively.

Each salary belongs to exactly one category. The input array can be of any length (including empty).

Thought Process

The core of this problem is categorization: for each salary, determine which of three defined ranges it falls into, and count how many are in each group.

A brute-force approach would involve iterating through the array and, for each salary, using conditional statements to increment the appropriate counter. This is straightforward because there are only three categories, and each salary can only belong to one.

There is no need for more advanced data structures like hash maps or sorting, since the categories are fixed and mutually exclusive. The only optimization possible is to minimize the number of conditional checks per salary.

In summary, the simplest and most efficient way is to use three counters and a single pass through the array.

Solution Approach

Let's break down the algorithm step-by-step:

1. Initialize counters: Create three variables to keep track of the count for each category: low, mid, and high. Set them all to zero at the start.
2. Iterate through the salaries: For each salary in the input array, use conditional statements to determine which category it belongs to.
   • If the salary is less than 40,000, increment low.
   • If the salary is at least 40,000 but less than 60,000, increment mid.
   • If the salary is 60,000 or more, increment high.
3. Return the results: After processing all salaries, return an array (or list) with the counts in the order: [low, mid, high].

This approach is efficient because it processes each salary exactly once, and uses only a constant amount of extra space.

Example Walkthrough

Let's go through an example step by step.

Suppose salaries = [35000, 40000, 45000, 60000, 75000, 39000].

• Start with low = 0, mid = 0, high = 0.
• First salary: 35000 → less than 40000 → low = 1
• Second salary: 40000 → 40000 ≤ salary < 60000 → mid = 1
• Third salary: 45000 → 40000 ≤ salary < 60000 → mid = 2
• Fourth salary: 60000 → salary ≥ 60000 → high = 1
• Fifth salary: 75000 → salary ≥ 60000 → high = 2
• Sixth salary: 39000 → less than 40000 → low = 2

Final result: [2, 2, 2] (2 low, 2 mid, 2 high).

Time and Space Complexity

Brute-force approach: Even a brute-force solution would still require examining every salary, so the time complexity is O(n), where n is the number of salaries.

Optimized approach: Our solution is already optimal:

• Time complexity: O(n) — We process each salary exactly once.
• Space complexity: O(1) — We use only three counters, regardless of input size.

There is no way to improve upon this, as every salary must be checked at least once.

Summary

The "Count Salary Categories" problem is a classic example of categorization and counting. By using three counters and a single pass through the input, we can efficiently and simply determine how many employees fall into each salary range. The approach is both intuitive and optimal, requiring only O(n) time and constant space.