algoadvance

You are given two arrays time1 and time2 both of length n. Each time1[i] and time2[i] represent times in the format HH:MM (24-hour clock) respectively. A pair (i, j) is said to form a complete day if time1[i] + time2[j] = 24:00. Your task is to count how many pairs (i, j) form a complete day.

Example 1:
Input: time1 = ["12:00", "18:00", "06:30"], time2 = ["12:00", "06:00", "17:30"]
Output: 2
Explanation: 
Pair (0, 0) => "12:00" + "12:00" = "24:00"
Pair (1, 1) => "18:00" + "06:00" = "24:00"

Example 2:
Input: time1 = ["14:30"], time2 = ["09:00"]
Output: 0
Explanation: No pair adds up to form a complete day.

Clarifying Questions

Before diving into the implementation, let’s clarify a few things:

  1. Are there any constraints on the inputs such as the maximum length of the arrays time1 and time2, and the format of the time strings?
  2. Can we assume that the input times are always valid and formatted correctly?

Strategy

  1. Convert Time to Minutes: Convert the times in time1 and time2 from HH:MM format to the number of minutes past midnight. This simplifies the addition and comparison process.
  2. Target Minutes Calculation: The target time in minutes for a complete day is 24:00, which equals 1440 minutes.
  3. Count Complements Using a Hash Map: Use a hash map to store the count of times (in minutes) from time2 and check for each time in time1 if its complement exists in the hash map.

Time Complexity

The overall time complexity is O(n).

Code

def convert_time_to_minutes(time):
    hours, minutes = map(int, time.split(':'))
    return hours * 60 + minutes

def count_pairs(time1, time2):
    target_minutes = 24 * 60  # 1440 minutes for a complete day
    
    # Convert all times to minutes
    time1_minutes = [convert_time_to_minutes(time) for time in time1]
    time2_minutes = [convert_time_to_minutes(time) for time in time2]
    
    # Create a frequency map for times in time2
    time2_count = {}
    for t in time2_minutes:
        if t not in time2_count:
            time2_count[t] = 0
        time2_count[t] += 1
    
    # Count valid pairs
    count = 0
    for t1 in time1_minutes:
        complement = target_minutes - t1
        if complement in time2_count:
            count += time2_count[complement]

    return count

# Example usage
time1 = ["12:00", "18:00", "06:30"]
time2 = ["12:00", "06:00", "17:30"]
print(count_pairs(time1, time2))  # Output: 2

This code converts times to minutes after midnight, counts pairs that sum to 24:00, and uses a hash map to efficiently track and count complements. This ensures that the solution is both clear and efficient.

Try our interview co-pilot at AlgoAdvance.com