algoadvance

Leetcode 3184. Count Pairs That Form a Complete Day I

Problem Statement

You are given a list of integers days, where each integer represents a number of hours worked on a day. A complete day is defined to be 24 hours or more.

You need to count how many pairs (i, j) exist, where i < j and the sum of days[i] + days[j] is greater than or equal to 24.

Clarifying Questions

  1. Should the input list days always have at least two elements?
  2. Are there any constraints on the values in the days list, such as non-negative integers?
  3. Do we need to consider the case where days[i] + days[j] equals exactly 24?
  4. What should be returned if no pairs meet the criteria?

Assuming typical constraints and conditions unless clarified otherwise.

Strategy

  1. Brute Force Approach:
    • Use two nested loops to consider all possible pairs (i, j) where i < j.
    • For each pair, check if the sum of days[i] + days[j] >= 24.
    • Count and return the number of valid pairs.
  2. Optimized Approach:
    • Sort the list days.
    • Use a two-pointer technique to count valid pairs.
      • Start with two pointers: one at the beginning (left) and one at the end (right) of the sorted list.
      • If the sum of the current pair is greater than or equal to 24, move the right pointer to the left.
      • If the sum is less than 24, move the left pointer to the right.
    • This approach ensures that we do not need to check all pairs, speeding up the solution compared to the brute force method.

Code

We will implement both approaches in C++.

Brute Force Approach

#include <vector>

int countPairsBruteForce(const std::vector<int>& days) {
    int count = 0;
    for (size_t i = 0; i < days.size(); ++i) {
        for (size_t j = i + 1; j < days.size(); ++j) {
            if (days[i] + days[j] >= 24) {
                ++count;
            }
        }
    }
    return count;
}

Optimized Approach

#include <vector>
#include <algorithm>

int countPairsOptimized(std::vector<int>& days) {
    std::sort(days.begin(), days.end());
    int count = 0;
    int left = 0;
    int right = days.size() - 1;

    while (left < right) {
        if (days[left] + days[right] >= 24) {
            // All pairs (left, right), (left, right-1), ... (left, left+1) are valid
            count += (right - left);
            --right;
        } else {
            ++left;
        }
    }

    return count;
}

Time Complexity

  1. Brute Force Approach:
    • Time Complexity: (O(n^2)), where n is the number of elements in days.
    • Space Complexity: (O(1)), since we are using only a constant amount of extra space.
  2. Optimized Approach:
    • Time Complexity: (O(n \log n)) due to the sorting step, and (O(n)) for the two-pointer traversal.
    • Space Complexity: (O(1)) if sorting in place, otherwise (O(n)) for extra space used by sort if not in place sort.

With these implementations, you can choose based on the size of the input for efficiency. The optimized approach is more efficient for larger datasets.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI