All challenges
Medium 0 solved 0% acceptance

Longest Run of Rolls

Find where the longest run of equal consecutive dice rolls starts and how long it is.

What you'll learn

  • Detect where a run of equal values ends
  • Keep the start and length of the best run
  • Break ties toward the first run

Problem

A dice simulator records every roll of a six-sided die in a list. A run is a group of consecutive rolls with the same value; a single roll is a run of length 1. Find the longest run. If several runs share the longest length, report the one that starts first.

Implement longest_run_of_rolls(rolls).

Input

rolls: The rolls in the order they happened, each from 1 to 6.

Output

Return [start, length]: the 0-based index where the longest run starts and its length. For an empty list return [-1, 0].

Constraints

0 ≤ number of rolls ≤ 10,000

1 ≤ roll ≤ 6

Examples

Example 1
Input:
rolls = [1, 4, 4, 2, 6, 6, 6, 3]

Expected output:
expected = [4, 3]
Input:
std::vector<long long> rolls = {1, 4, 4, 2, 6, 6, 6, 3};

Expected output:
std::vector<long long> expected = {4, 3};
Input:
long[] rolls = new long[] {1, 4, 4, 2, 6, 6, 6, 3};

Expected output:
long[] expected = new long[] {4, 3};

Explanation

The three 6s starting at index 4 beat the two 4s: [4, 3].

Example 2
Input:
rolls = [5, 5, 2, 2, 3]

Expected output:
expected = [0, 2]
Input:
std::vector<long long> rolls = {5, 5, 2, 2, 3};

Expected output:
std::vector<long long> expected = {0, 2};
Input:
long[] rolls = new long[] {5, 5, 2, 2, 3};

Expected output:
long[] expected = new long[] {0, 2};

Explanation

Both pairs have length 2; the 5s start first, at index 0: [0, 2].

How to approach it

Try on your own first, then open one hint at a time.

Hint 1

Remember where the current run started.

Hint 2

When the value changes (or the list ends), compare the finished run with the best one.

Hint 3

Replace the best only when the new run is strictly longer.

Expected complexity

O(n) time, O(1) extra space

References

This challenge is adapted for CodeUtility. Follow the statement and constraints above.

The best passing solution of each coder. Faster, smaller and better-reviewed solutions rank higher.

No passing solutions yet. Solve it to take first place.

Learn from others

Community solutions

No published solutions yet. Solve this challenge to share the first one.