23. Trip Duration’s Movies

Question: Given a list of movie length and trip duration, find if there are two movie durations where their sum equals the trip duration.

For example, given [3, 7, 9, 2, 1] and 12, you should return true (3 + 9 == 12),

For example, given [3, 7, 9, 2, 1] and 15, you should return false.

Hints:

- You need a data structure to remember what you already saw,

- It’s a two-sum problem.

Solution:

func isThereAny2Movies(tripDuration: Int, movieDurations: [Int]) -> Bool {
  // 1.
  guard tripDuration > 0 else { return false }
  guard !movieDurations.isEmpty else { return false }
  // 2.
  var durations = Set<Int>()
  for movieDuration in movieDurations where movieDuration < tripDuration {
    // 3.
    let remainingTime = tripDuration - movieDuration
    // 4.
    if durations.contains(remainingTime) {
      return true
    }
    // 5.
    durations.insert(movieDuration)
  }
  // 6.
  return false
}

Explanations:

1. If the trip duration is not greater than 0 or if the movie duration is empty, there aren’t two trips that can match, return false.

guard tripDuration > 0 else { return false }
guard !movieDurations.isEmpty else { return false }

2. Let’s create a set to save durations we saw, and let’s iterate over the movie durations (only if the movie duration is lesser than the trip duration).

var durations = Set<Int>()
for movieDuration in movieDurations where movieDuration < tripDuration {

3. Let’s find the remaining time from the current movie and the total duration of the trip.

let remainingTime = tripDuration — movieDuration

4. If the remaining time exists in the saved durations, we have a matching pair of movies that equal the trip duration, then return true.

if durations.contains(remainingTime) {
  return true
}

5. Insert the current movie duration into the saved durations set.

durations.insert(movieDuration)

6. We didn’t find any pair; return false.

return false

Complexity:

- Time Complexity: As we browse all movies, the time complexity is linear O(n),

- Space Complexity: As we might save all movies, the space complexity is linear O(n).

Test-cases:

public func testIsThereAny2Movies() {
  let movieDurations = [3, 7, 9, 2, 1]
  assert(isThereAny2Movies(tripDuration: 12, movieDurations: movieDurations) == true, "isThereAny2Movies 12 not equal")
  assert(isThereAny2Movies(tripDuration: 15, movieDurations: movieDurations) == false, "isThereAny2Movies 15 not equal")
}

Follow-up:

No follow-up question.

<< More Interview Questions | Data Structures and Algorythms >>