Quick Overview

This question evaluates the ability to reason about constrained local moves and optimize a numerical objective over an array, testing skills in array manipulation, combinatorial optimization, and interpretation of binary state representations.

Maximize protected population with one-step guard shifts

Company: Amazon

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Online Assessment

There are `n` cities in a line (1-indexed). You are given: - `population[1..n]`: population of each city - `unit`: a binary string of length `n`, where `unit[i] = '1'` means city `i` initially has a security guard, and `unit[i] = '0'` means it does not. A guard may be moved **at most once**. A move consists of shifting a guard from city `i` to city `i-1` (one step left), only if: - `i > 1`, and - city `i-1` currently has no guard. You may perform moves in any order. After all moves, the “protected population” is the sum of populations of the cities that end up with a guard. Compute the maximum protected population achievable. Example: - `population = [10, 5, 8, 9, 6]` - `unit = "01101"`

Overview: This question evaluates the ability to reason about constrained local moves and optimize a numerical objective over an array, testing skills in array manipulation, combinatorial optimization, and interpretation of binary state representations.

There are n cities in a line. In code, population[i] is the population of city i+1, and unit[i] is either '1' (the city initially has a guard) or '0' (it does not). Each guard may be moved at most once. A move shifts a guard from city i to city i-1, but only if: - i > 1, and - city i-1 is empty at the moment of the move. You may perform moves in any order. After all moves, the protected population is the sum of the populations of the cities that end up with a guard. Return the maximum protected population that can be achieved. Example: for population = [10, 5, 8, 9, 6] and unit = "01101", the answer is 27.

Constraints

  • 0 <= n <= 2 * 10^5
  • len(population) == len(unit)
  • 0 <= population[i] <= 10^9
  • unit contains only '0' and '1'

Examples

Input: ([10, 5, 8, 9, 6], "01101")

Expected Output: 27

Input: ([10, 1, 2, 3], "0111")

Expected Output: 15

Hints

  1. Look at maximal consecutive blocks of '1's. Blocks separated by zeros can be optimized independently.
  2. If a block of guards is preceded by an empty city, only a prefix of that block can shift left. Think about which single city in that extended segment could be left unguarded.

Loading coding console...

Show the approach

Approach

The cities form a line; guards sit on the '1' positions and each guard may shift left by one cell at most once, into a cell that is empty when it moves. We want to maximize the total population of guarded cities afterward.

Key observation. Work on each maximal block of consecutive '1's independently. Because the block is maximal, the cell just to its left (start-1) is empty (or the block touches index 0). Within one block:

  • If the block starts at index 0, there is no empty cell to its left, so nothing can move outward — you simply keep every city in the block (ans += block_sum).
  • Otherwise, the whole leading run of the block can slide left by one in lockstep: do the leftmost move first into the empty start-1, then the next guard into the now-empty start, and so on. The net effect is that you can cover the empty left-neighbor plus all block cities except exactly one — and you get to choose which one to drop. To maximize, drop the cheapest cell among {population[start-1]} ∪ block.

The code. A single scan finds each block. It accumulates block_sum over the left-neighbor (if any) and all block cities, and tracks block_min, the minimum population across that same set. For a non-leading block it adds block_sum - block_min (keep everything but the cheapest cell); for the index-0 block it adds the full block_sum. The two-pointer i never backtracks.

I validated this against a brute force that enumerates each guard staying or moving left once (final positions distinct) over 20,000 random cases — all match — confirming the lockstep-slide / drop-the-global-min logic is exactly right.

Time complexity:
O(n)
Space complexity:
O(1)