Number of Employees Who Met the Target

Easy

Asked by:

30 views

Topics:

Arrays

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⁵

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the possible ranges for the numbers in the `performance` array and the `target` value?
Can the `performance` array be empty, or can the `target` be zero?
Are the performance values integers or floating-point numbers?
If no employees meet the target, what should the function return?
Can there be duplicate performance values in the `performance` array?

Brute Force Solution

Approach

We want to find out how many employees reached a specific goal. The brute force method involves looking at each employee's performance individually and comparing it to the target. We then count the number of employees who achieved the target.

Here's how the algorithm would work step-by-step:

Take the performance score of the first employee.
Compare that score to the target value.
If the employee's score is greater than or equal to the target, mark them as having met the target.
Repeat steps 1-3 for every employee, one by one.
After checking all employees, count how many employees were marked as having met the target.
The final count is the answer to the question.

Code Implementation

def number_of_employees_who_met_target(employee_performance, target_value):
    employees_who_met_target = 0

    # Iterate through each employee's performance.
    for individual_score in employee_performance:

        # Check if the current employee met the target.
        if individual_score >= target_value:

            # Increment the counter if the employee met the target.
            employees_who_met_target += 1

    return employees_who_met_target

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through each employee's performance score in the input array once. For each employee, it performs a single comparison against the target value. This single pass through the n employees results in n comparisons. Therefore, the time complexity is directly proportional to the number of employees, making it O(n).

Space Complexity

O(1) – The algorithm iterates through each employee's performance score and compares it to the target. It maintains a count of employees who met the target. The only extra memory used is a single variable to store the count of employees who met the target, which does not depend on the number of employees (N). Therefore, the auxiliary space complexity is constant.

Optimal Solution

Approach

The problem asks us to find how many employees reached a certain performance target. Instead of checking each employee's performance individually, we can use a more efficient counting method. This will help us quickly determine the number of employees who met or exceeded the target.

Here's how the algorithm would work step-by-step:

Go through the list of employees' performance values one by one.
For each employee, check if their performance is equal to or greater than the specified target.
If an employee's performance meets or exceeds the target, increase a counter by one.
After checking all employees, the counter will hold the total number of employees who met the target.
Return the final count.

Code Implementation

def number_of_employees_who_met_the_target(employee_performance, target):
    employees_meeting_target = 0

    # Iterate through each employee's performance.
    for performance_value in employee_performance:
        #Check if the current employee met the target
        if performance_value >= target:

            employees_meeting_target += 1

    return employees_meeting_target

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the list of employee performance values once. For each employee's performance, it performs a single comparison against the target. Therefore, the number of operations grows linearly with the number of employees, n. The total operations approximate to 'n' comparisons, resulting in a time complexity of O(n).

Space Complexity

O(1) – The algorithm uses a single integer variable, the counter, to keep track of the number of employees who met the target. The space used by this counter remains constant irrespective of the number of employees. Therefore, the auxiliary space complexity is O(1).

Edge Cases

Case	How to Handle
Empty performance array	Return 0 if the input array is empty as no employee met the target.
Null performance array	Throw an IllegalArgumentException or return a designated error value (e.g., -1) to signal an invalid input.
Target is negative	Handle negative targets by comparing each performance with the target.
Target is very large (potential overflow if summing performances)	Ensure that the performance values and target are within reasonable bounds to prevent integer overflow during comparisons or calculations.
Array contains very large performance values	Ensure that the data type used to store performance values can accommodate potentially large numbers to prevent overflow.
All performance values are zero	Correctly count employees meeting target even when all values are zero and target is zero or negative.
All performance values are equal and target equals the performance value	Return the number of employees, as they all meet the target.
Performance values are doubles/floats rather than integers	Use appropriate comparison with a small epsilon to account for floating-point precision issues.

Empty performance array

How to Handle:

Return 0 if the input array is empty as no employee met the target.

Null performance array

How to Handle:

Throw an IllegalArgumentException or return a designated error value (e.g., -1) to signal an invalid input.

Target is negative

How to Handle:

Handle negative targets by comparing each performance with the target.

Target is very large (potential overflow if summing performances)

How to Handle:

Ensure that the performance values and target are within reasonable bounds to prevent integer overflow during comparisons or calculations.

Array contains very large performance values

How to Handle:

Ensure that the data type used to store performance values can accommodate potentially large numbers to prevent overflow.

All performance values are zero

How to Handle:

Correctly count employees meeting target even when all values are zero and target is zero or negative.

All performance values are equal and target equals the performance value

How to Handle:

Return the number of employees, as they all meet the target.

Performance values are doubles/floats rather than integers

How to Handle:

Use appropriate comparison with a small epsilon to account for floating-point precision issues.