Katkat
Back

Find longest run of identical consecutive shows

NetflixSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This question tests the ability to track state while iterating through an array to identify the longest contiguous sub-sequence of identical elements.

Problem Statement

You are given a list of integers, shows, where each integer represents a show ID. A 'run' is defined as a contiguous sub-sequence of the array where all elements are the same. Your task is to find the length of the longest run in the list.

Function Signature

def longest_show_run(shows: list[int]) -> int:

Examples

Example 1: Input: shows = [101, 101, 202, 303, 303, 303, 404] Output: 3 Explanation: The longest run is [303, 303, 303], which has length 3.

Example 2: Input: shows = [1, 2, 3] Output: 1 Explanation: Each show is distinct, so the longest run is 1.

Constraints

  • 0 <= len(shows) <= 10^6
  • Elements are non-negative integers.
  • Your solution should have O(n) time complexity and O(1) auxiliary space.

Edge Cases

  • Empty array: The result should be 0.
  • Array with a single element: The result should be 1.
  • Array where all elements are identical: The result should be len(shows).

Hints

Hint 1

Initialize two variables: one to track the length of the current run and another to store the maximum length found so far.

Hint 2

Iterate through the array starting from the second element, comparing the current element with the previous one.

Hint 3

If the current element matches the previous one, increment your current run counter; otherwise, reset the current counter to 1.

Follow-up questions

  • How would you modify your solution to return the starting index and the ID of the longest run?
  • If the input were provided as a stream of data that doesn't fit in memory, how would you approach the problem?
  • What if the input was a 2D grid of shows and you had to find the longest run of identical shows horizontally or vertically?