Number of Employees Who Met the Target

Easy

#2505Time: O(n log n), where n is the number of employees. The dominant operation is sorting the `hours` array. The subsequent linear scan to find the first element meeting the target takes at most O(n) time.Space: O(log n) to O(n). The space complexity depends on the sorting algorithm used. In Java, `Arrays.sort()` for primitive types uses a dual-pivot quicksort, which has an average space complexity of O(log n) for the recursion stack. The worst-case space complexity can be O(n).1 company

Data structures

Array

Companies

tcs

Prompt

There are n employees in a company, numbered from 0 to n - 1. Each employee i has worked for hours[i] hours in the company.

The company requires each employee to work for at least target hours.

You are given a 0-indexed array of non-negative integers hours of length n and a non-negative integer target.

Return the integer denoting the number of employees who worked at least target hours.

Example 1:

Input: hours = [0,1,2,3,4], target = 2
Output: 3
Explanation: The company wants each employee to work for at least 2 hours.
- Employee 0 worked for 0 hours and didn't meet the target.
- Employee 1 worked for 1 hours and didn't meet the target.
- Employee 2 worked for 2 hours and met the target.
- Employee 3 worked for 3 hours and met the target.
- Employee 4 worked for 4 hours and met the target.
There are 3 employees who met the target.

Example 2:

Input: hours = [5,1,4,2,2], target = 6
Output: 0
Explanation: The company wants each employee to work for at least 6 hours.
There are 0 employees who met the target.

Constraints:

1 <= n == hours.length <= 50
0 <= hours[i], target <= 10⁵

Approaches

2 approaches with complexity analysis and trade-offs.

This approach involves first sorting the hours array. Once sorted, we can efficiently find the number of employees who met the target. After finding the first employee who meets the criteria in the sorted list, all subsequent employees will also meet it, allowing for a quick calculation of the total count.

Algorithm

Sort the input array hours in non-decreasing order.
Iterate through the sorted hours array from the beginning.
Find the first index i where hours[i] is greater than or equal to the target.
The number of employees who met the target is n - i, where n is the total number of employees. Return this value.
If the loop finishes without finding such an employee, return 0.

Walkthrough

The core idea is that if we sort the hours worked by employees in ascending order, all employees who met the target will form a contiguous block at the end of the array. By finding the start of this block, we can determine its size.

Algorithm

Sort the input array hours in non-decreasing order.
Iterate through the sorted hours array from the beginning.
Find the first index i where hours[i] is greater than or equal to the target.
Once this index i is found, we know that all elements from this index to the end of the array meet the target. The total count is therefore the total number of employees n minus the current index i (i.e., n - i).
Return this count immediately.
If the loop completes without finding any employee who met the target, it means no one did, so we return 0.

Code Snippet

1import java.util.Arrays;2 3class Solution {4    public int numberOfEmployeesWhoMetTarget(int[] hours, int target) {5        Arrays.sort(hours);6        int n = hours.length;7        for (int i = 0; i < n; i++) {8            if (hours[i] >= target) {9                return n - i;10            }11        }12        return 0;13    }14}

Complexity

Time

O(n log n), where n is the number of employees. The dominant operation is sorting the `hours` array. The subsequent linear scan to find the first element meeting the target takes at most O(n) time.

Space

O(log n) to O(n). The space complexity depends on the sorting algorithm used. In Java, `Arrays.sort()` for primitive types uses a dual-pivot quicksort, which has an average space complexity of O(log n) for the recursion stack. The worst-case space complexity can be O(n).

Trade-offs

Pros

After sorting, a binary search could also be used to find the first valid employee, which could be slightly faster in practice for the search part (O(log n)) than a linear scan, though the overall complexity remains O(n log n).

Cons

The time complexity of O(n log n) is suboptimal for this problem.
It modifies the input array in-place. If the original order of the array needs to be preserved, a copy must be made, which would increase the space complexity to O(n).

This is the most straightforward and optimal approach. We can solve the problem by iterating through the hours array just once. We maintain a counter, and for each employee, we check if their hours worked are greater than or equal to the target. If they are, we increment the counter.

Algorithm

Initialize a counter count to 0.
Iterate through each hour in the hours array.
If hour is greater than or equal to target, increment count.
After the loop, return count.

Walkthrough

The problem asks for a simple count of elements that satisfy a condition. There is no need for any pre-processing like sorting. A single pass through the array is sufficient to gather the required information. This approach directly translates the problem statement into code.

Algorithm

Initialize a counter variable, count, to 0.
Iterate through each element h in the hours array.
For each h, check if it is greater than or equal to the target.
If the condition h >= target is true, increment the count.
After the loop has processed all elements in the array, return the final count.

This logic can be implemented using a standard for-each loop for simplicity and readability, or with Java Streams for a more functional style.

Code Snippet (For-Each Loop)

1class Solution {2    public int numberOfEmployeesWhoMetTarget(int[] hours, int target) {3        int count = 0;4        for (int h : hours) {5            if (h >= target) {6                count++;7            }8        }9        return count;10    }11}

Code Snippet (Java Streams)

1import java.util.Arrays;2 3class Solution {4    public int numberOfEmployeesWhoMetTarget(int[] hours, int target) {5        return (int) Arrays.stream(hours)6                             .filter(h -> h >= target)7                             .count();8    }9}

Complexity

Time

O(n), where n is the number of employees. We must visit each element of the `hours` array exactly once to check if it meets the target.

Space

O(1). We only use a constant amount of extra space for the counter variable, regardless of the input size.

Trade-offs

Pros

Optimal time complexity, as every element must be checked at least once.
Optimal space complexity, using only a single extra variable.
Simple, intuitive, and easy to implement.
Does not modify the input array.

Cons

There are no significant disadvantages to this approach as it is the optimal solution for this problem.

Solutions

Solution

1class Solution {2public:3  int numberOfEmployeesWhoMetTarget(vector<int> &hours, int target) {4    int ans = 0;5    for (int x : hours) {6      ans += x >= target;7    }8    return ans;9  }10};

1class Solution:2    def numberOfEmployeesWhoMetTarget(3        self, hours: List[int], target: int) -> int: return sum(x >= target for x in hours)

1class Solution {2public3  int numberOfEmployeesWhoMetTarget(int[] hours, int target) {4    int ans = 0;5    for (int x : hours) {6      if (x >= target) {7        ++ans;8      }9    }10    return ans;11  }12}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem