Search⌘ K
AI Features
Home
Courses
Grokking the Coding Interview Patterns in Python

Solution: Binary Watch

Understand how to apply backtracking to solve the binary watch problem by exploring all LED combinations to generate valid times. Learn to implement recursive functions that track positions, hours, and minutes, while efficiently pruning invalid solutions. This lesson helps you master recursive problem solving and backtracking techniques for combinatorial challenges.

We'll cover the following...

Statement

A binary watch has 4 LEDs for displaying hours (ranging from 0 to 11) and 6 for displaying minutes (ranging from 0 to 59). Each LED can be on (1) or off (0), with the least significant bit on the right. For example, the binary watch below reads “9:22.”

Given an integer enabled, which represents the number of LEDs currently turned on, return all possible times that the watch could display. You may return the answer in any order.

Note: Remember the following regarding leading zeros:

  • The hour cannot have a leading zero (e.g., “01:00” is invalid, it should be “1:00”).

  • The minute must be two digits and may include a leading zero (e.g., “10:2” is invalid, it should be “10:02”).

Constraints:

  • 0≤0 \leq enabled ≤10\leq 10

Solution

The core intuition behind solving this problem is to use backtracking to explore all possible configurations of the LEDs that can be turned on. Because there are 1010 possible LED positions (44 for hours and 66 for minutes), we recursively try each position, updating the values for hours and minutes based on which LED is turned on. We check whether the time is valid once the required LEDs are turned on. If it is valid, the time is stored. After each recursive step, we backtracked by undoing the previous changes, allowing us to explore other possible combinations of LEDs turned on.

Using the above intuition, we create a recursive function, BinaryWatchRec, to try all possible configurations of LEDs being turned on. We implement the recursive function as follows:

  1. The parameters that BinaryWatchRec takes are as follows:

    1. position: Tracks the current LED position (from 00 to 99 ...