Leetcode – Number of Students Doing Homework at a Given Time Solution

Spread the love

Leetcode is a go-to platform for aspiring software engineers and data scientists who aim to sharpen their coding skills by solving an array of challenges that span multiple categories. Among these challenges is a seemingly trivial but instructive problem known as “Number of Students Doing Homework at a Given Time”. This problem falls under the category of array manipulation and condition checks.

In this article, we’ll go through:

  1. The Problem Statement
  2. Initial Thoughts and Brute-force Approach
  3. An Optimized Approach
  4. Python Code Implementations
  5. Test Cases and Edge Cases
  6. Time and Space Complexity Analysis
  7. Conclusion

1. Problem Statement

Given two integer arrays startTime and endTime, and an integer queryTime, the task is to return the number of students doing their homework at queryTime. More formally, return the number of students where queryTime lays in the interval [startTime[i], endTime[i]] inclusive.

Example 1:

Input: startTime = [1, 2, 3], endTime = [3, 2, 7], queryTime = 4
Output: 1
Explanation: We have 3 students where:

  • The first student started doing homework at time 1 and finished at time 3 and wasn’t doing homework at 4.
  • The second student started at time 2 and finished at time 2 and also wasn’t doing homework at 4.
  • The third student started at time 3 and finished at time 7 and was the only student doing homework at 4.

2. Initial Thoughts and Brute-force Approach

A simple, straightforward approach to solving this problem is by iterating over each student’s start and end times, checking whether the queryTime falls within that range, and incrementing a counter if it does.

3. An Optimized Approach

In this case, there isn’t much room to optimize further because we need to check each student’s time range at least once. Therefore, the best we can do is O(n)O(n) time complexity, where nn is the number of students.

4. Python Code Implementations

Brute-force Implementation

def busyStudent(startTime, endTime, queryTime):
    count = 0
    for i in range(len(startTime)):
        if startTime[i] <= queryTime <= endTime[i]:
            count += 1
    return count

“Optimized” Implementation

As mentioned earlier, the problem doesn’t leave much scope for optimization beyond O(n)O(n), so the optimized solution is the same as the brute-force approach.

5. Test Cases and Edge Cases

Here are some test cases, including edge cases, to validate the implementation:

# Test 1
assert busyStudent([1, 2, 3], [3, 2, 7], 4) == 1
# Test 2
assert busyStudent([4], [4], 4) == 1
# Test 3 (Edge Case)
assert busyStudent([1], [3], 3) == 1
# Test 4 (Edge Case)
assert busyStudent([9,8,7,6,5,4,3,2,1], [10,10,10,10,10,10,10,10,10], 5) == 5

6. Time and Space Complexity Analysis

Time Complexity

Both the brute-force and the optimized solution have a time complexity of O(n) where n is the number of students. This is because we have to iterate through all the start and end times at least once.

Space Complexity

The space complexity for both solutions is O(1) as we are only using a constant amount of additional space to store the count variable.

7. Conclusion

The “Number of Students Doing Homework at a Given Time” problem on LeetCode is a straightforward problem that focuses on array traversal and condition checking. Although the problem is simple and doesn’t offer much scope for optimization, it’s still an excellent exercise for beginners to get comfortable with array manipulations and if-else conditionals in Python.

Leave a Reply