Katkat
Back

Cheapest Daily Shirt Colors With No Color Repeated on Consecutive Days

OpenAISoftware Engineer · Technical Screen
HardSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

Pick a blue, green or red shirt for each of n days so that the total price is as low as possible while never buying the same color on two consecutive days, and return the chosen color sequence. It tests dynamic programming over a small state space and reconstruction of the optimal choices.

A store has a sale on blue, green and red shirts for the next n days. On day i, a blue shirt costs blue_costs[i] dollars, a green shirt costs green_costs[i] dollars, and a red shirt costs red_costs[i] dollars. You want to buy exactly one shirt on each of the n days, but you cannot buy the same color on two consecutive days.

Return the color to buy on each day so that the total cost of the n shirts is minimized.

Function Signature

def lowest_cost(blue_costs: list[int], green_costs: list[int], red_costs: list[int]) -> list[str]:

Day i corresponds to index i of each list, starting from 0.

Rules

  • Return a list of length n whose element i is 'b', 'g' or 'r': the color of the shirt bought on day i.
  • Two adjacent elements of the returned list must differ.
  • The total cost is the sum, over all days, of the price of the color chosen that day, and it must be the minimum over all valid color sequences.
  • The input guarantees that exactly one valid color sequence achieves the minimum, so the answer is unique.

Constraints

  • 1 <= n <= 10^5, and the three lists all have length n.
  • Every price is an integer with 1 <= price <= 10^4, so every total is at most 10^9 and fits in a 32-bit signed integer.
  • Exactly one valid color sequence has the minimum total cost.

Examples

Example 1

Input: blue_costs = [1, 1, 1], green_costs = [3, 5, 7], red_costs = [4, 6, 4]
Output: ['b', 'g', 'b']

The total is 1 + 5 + 1 = 7. Buying blue every day would be cheapest, but two consecutive days cannot have the same color.

Example 2

Input: blue_costs = [18, 12, 1, 9], green_costs = [13, 15, 7, 9], red_costs = [12, 16, 4, 8]
Output: ['r', 'g', 'b', 'r']

The total is 12 + 15 + 1 + 8 = 36.

Example 3

Input: blue_costs = [100, 1, 76, 14], green_costs = [22, 20, 1, 2], red_costs = [99, 99, 5, 12]
Output: ['g', 'b', 'r', 'g']

The total is 22 + 1 + 5 + 2 = 30. Green on day 2 costs only 1, but taking it would force a color other than green on day 3, where green is the cheapest at 2; the unique optimum takes red on day 2 instead.