FastPrepHouse Robber with Selected Indices
Problem · Array

House Robber with Selected Indices

Learn this problem
● MediumGoogle logoGoogleNEW GRADPHONE SCREEN
See Google hiring insights

Problem statement

Each element of points is the number of points available at one index. Choose any set of indices such that no two chosen indices are adjacent and the sum of their values is as large as possible.

Return a ragged long[][] with two rows. Row 0 contains only the maximum sum. Row 1 contains the chosen zero-based indices in increasing order.

Use this deterministic tie rule: while reconstructing from right to left using optimal prefix sums, choose index i only when taking it gives a strictly larger sum than skipping it; on equality, skip i. Choosing no index is allowed.

Function

robWithIndices(points: int[]) → long[][]

Examples

Example 1

points = [2,7,9,3,1]return = [[12],[0,2,4]]

Indices 0, 2, and 4 are non-adjacent and contribute 2 + 9 + 1 = 12.

Example 2

points = [2,2]return = [[2],[0]]

Either index gives sum 2. At index 1 taking and skipping tie, so the rule skips it and keeps index 0.

Example 3

points = [0,0,0]return = [[0],[]]

Every take decision ties with skipping, so the deterministic strategy returns the empty selection with maximum sum zero.

Constraints

  • 0 <= points.length <= 200000
  • 0 <= points[i] <= 1000000000
  • The maximum sum must be computed with signed 64-bit arithmetic.

More Google problems

drafts saved locally
public long[][] robWithIndices(int[] points) {
    // Write your code here.
}
points[2,7,9,3,1]
expected[[12],[0,2,4]]
checking account