2798. Number of Employees Who Met the Target

EasyArrayEnumeration
Leetcode Link

Problem Description

In this problem, there is a company with n employees, each of whom is assigned a unique number from 0 to n - 1. We are provided with an array called hours, which is indexed from 0. The value at each index i in this array represents the number of hours employee i has worked. The company has also set a minimum required number of hours that each employee must meet or exceed, which is specified by a target variable.

The objective is to determine how many employees have worked for at least target hours. This is an example of a counting problem where we need to count the number of elements in an array that meet a particular condition.

Intuition

The intuition behind the solution is very straightforward. Since we need to count the number of employees who have met or exceeded the target hours, we can iterate through the hours array and compare each employee's hours with the target. Every time we find an employee whose hours are greater than or equal to target, we increment our count.

We arrive at the solution approach by recognizing that it's a direct application of the concept of iteration and comparison. Each employee's hours worked are independently compared to target, and if they satisfy the condition x >= target, they are included in our count.

In Python, this can be neatly expressed in a single line using a generator expression inside the sum() function, which iterates through each element x in hours and evaluates the condition x >= target. The sum() function effectively counts the number of True evaluations, which corresponds to the number of employees who have met the target hours.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Which of the following is the prefix sum of array [1, 2, 3, 4, 5]?

Solution Approach

The implementation of the solution employs a simple approach that does not necessarily rely on complex algorithms, data structures, or patterns. It uses Python's built-in features to perform the operation efficiently and with clarity.

The solution is to use a generator expression inside the sum() function. A generator expression is a concise way to create a generator on the fly without the overhead of loops or the need to define a generator function. In this case, the expression (x >= target for x in hours) generates a sequence of boolean values (True or False). Each boolean value corresponds to whether an individual employee's hours worked is greater than or equal to the target.

The sum() function then takes this sequence of booleans and counts the number of True values. In Python, True is equivalent to 1 and False is equivalent to 0 when performing arithmetic operations, so summing a sequence of booleans effectively counts the number of True values.

To step through the code:

  1. hours is a list of integers, where each integer represents the hours worked by an employee.
  2. target is an integer representing the target number of hours that employees should meet or exceed.
  3. The generator expression (x >= target for x in hours) iterates over each element x in hours.
  4. For each x, it checks whether x >= target. This returns True if the condition is met, and False otherwise.
  5. The sum() function adds up all the True values, effectively counting them.
  6. The final returned value is the total count of employees who have worked at least target hours.

No additional data structures are needed for this approach, and its time complexity is O(n), where n is the number of employees, since it involves a single pass through the hours list.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What are the most two important steps in writing a depth first search function? (Select 2)

Example Walkthrough

Let's use a small example to depict how the solution approach is applied to determine the number of employees who have met or exceeded the target number of hours.

Suppose we have a company with 5 employees and the following hours they have worked: hours = [6, 2, 9, 4, 7]. The company has set a minimum required number of hours (target) to be 5.

Now, let's walk through the solution step by step:

  1. We have our hours list: [6, 2, 9, 4, 7].
  2. Our target is 5.
  3. We construct a generator expression: (x >= target for x in hours) which we will use to iterate over the hours.
  4. As we iterate through the hours, we compare each value (each employee's hours) with the target:
    • 6 >= 5 --> True
    • 2 >= 5 --> False
    • 9 >= 5 --> True
    • 4 >= 5 --> False
    • 7 >= 5 --> True
  5. We then pass the generator expression to the sum() function, which will process the boolean values:
    • sum([True, False, True, False, True]) is the same as sum([1, 0, 1, 0, 1])
  6. The sum() function counts the number of 1s (or True values), which is 3 in this case.

The final output of this operation is 3, which means 3 employees have worked at least the target number of hours 5. The steps we followed are not only intuitive but also concise and efficient, resulting in an elegant solution to our counting problem.

Solution Implementation

1class Solution:
2    def number_of_employees_who_met_target(self, hours: List[int], target: int) -> int:
3        # Initialize the count of employees who meet or exceed the target hours
4        count_met_target = 0
5      
6        # Iterate through the list of employee hours
7        for employee_hours in hours:
8            # If an employee meets or exceeds the target, increment the counter
9            if employee_hours >= target:
10                count_met_target += 1
11      
12        # Return the total count of employees who met or exceeded the target hours
13        return count_met_target
14
1class Solution {
2    // Method to count the number of employees who have met or exceeded the target number of hours
3    public int numberOfEmployeesWhoMetTarget(int[] hoursWorked, int targetHours) {
4        // Initialize a counter to keep track of the employees meeting the target
5        int numberOfEmployeesMeetingTarget = 0;
6
7        // Iterate through the hours worked by each employee
8        for (int hours : hoursWorked) {
9            // If the employee has worked hours greater than or equal to the target, increment the counter
10            if (hours >= targetHours) {
11                numberOfEmployeesMeetingTarget++;
12            }
13        }
14
15        // Return the total count of employees who have met or exceeded the target hours
16        return numberOfEmployeesMeetingTarget;
17    }
18}
19
1class Solution {
2public:
3    // This function counts and returns the number of employees who have worked at least 'target' number of hours.
4    int numberOfEmployeesWhoMetTarget(vector<int>& hours, int target) {
5        int count = 0; // Initialize the count of employees meeting the target
6      
7        // Iterate over the vector containing hours worked by each employee
8        for (int workedHours : hours) {
9            // If the current employee's hours are greater than or equal to the target, increment the count
10            if (workedHours >= target) {
11                count++;
12            }
13        }
14      
15        // Return the final count of employees who met or exceeded the target hours
16        return count;
17    }
18};
19
1// Calculates the number of employees who have met or exceeded a target number of work hours.
2// @param {number[]} workHours - An array representing the number of hours worked by each employee.
3// @param {number} targetHours - The target number of hours that employees should meet or exceed.
4// @returns {number} The count of employees who have met or exceeded the target hours.
5function numberOfEmployeesWhoMetTarget(workHours: number[], targetHours: number): number {
6    let count = 0; // Initialize a counter for the employees meeting the target.
7  
8    // Iterate over the array of work hours.
9    for (const hoursWorked of workHours) {
10        // If this employee's hours are greater than or equal to the target, increment the counter.
11        if (hoursWorked >= targetHours) {
12            count++;
13        }
14    }
15  
16    return count; // Return the total count of employees meeting the target.
17}
18
Not Sure What to Study? Take the 2-min Quiz：

Problem: Given a list of tasks and a list of requirements, compute a sequence of tasks that can be performed, such that we complete every task once while satisfying all the requirements.

Which of the following method should we use to solve this problem?

Time and Space Complexity

Time Complexity:

The given code has a single list comprehension that iterates over the list of hours once and checks if each element is greater than or equal to the given target. This operation is O(n) where n is the number of elements in the hours list. Hence, the time complexity of the code is O(n).

Space Complexity:

This code does not use any additional space that scales with the size of the input except for a few variables to keep track of the sum. As a result, the space complexity is O(1) using a constant amount of extra space.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

What's the output of running the following function using input 56?

1KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13    def dfs(path, res):
14        if len(path) == len(digits):
15            res.append(''.join(path))
16            return
17
18        next_number = digits[len(path)]
19        for letter in KEYBOARD[next_number]:
20            path.append(letter)
21            dfs(path, res)
22            path.pop()
23
24    res = []
25    dfs([], res)
26    return res
27
1private static final Map<Character, char[]> KEYBOARD = Map.of(
2    '2', "abc".toCharArray(),
3    '3', "def".toCharArray(),
4    '4', "ghi".toCharArray(),
5    '5', "jkl".toCharArray(),
6    '6', "mno".toCharArray(),
7    '7', "pqrs".toCharArray(),
8    '8', "tuv".toCharArray(),
9    '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13    List<String> res = new ArrayList<>();
14    dfs(new StringBuilder(), res, digits.toCharArray());
15    return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19    if (path.length() == digits.length) {
20        res.add(path.toString());
21        return;
22    }
23    char next_digit = digits[path.length()];
24    for (char letter : KEYBOARD.get(next_digit)) {
25        path.append(letter);
26        dfs(path, res, digits);
27        path.deleteCharAt(path.length() - 1);
28    }
29}
30
1const KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13    let res = [];
14    dfs(digits, [], res);
15    return res;
16}
17
18function dfs(digits, path, res) {
19    if (path.length === digits.length) {
20        res.push(path.join(''));
21        return;
22    }
23    let next_number = digits.charAt(path.length);
24    for (let letter of KEYBOARD[next_number]) {
25        path.push(letter);
26        dfs(digits, path, res);
27        path.pop();
28    }
29}
30

Recommended Readings

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Runtime to Algo Cheat Sheet

Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫