Bird
Raised Fist0
Interview Prepgreedy-algorithmsmediumAmazonGoogleBloomberg

Partition Labels

Choose your preparation mode4 modes available
Try ItSolutionTrace

Start learning this pattern below

Jump into concepts and practice - no test required

or
Recommended
Test this pattern10 questions across easy, medium, and hard to know if this pattern is strong
▶
Steps
setup

Initialize last occurrence array

Create an array 'last' of size 26 initialized to zero to store the last occurrence index of each character.

💡 This array will help quickly find the farthest index each character appears at, which is crucial for partitioning.
Line:last = [0] * 26
💡 We prepare a data structure to record last occurrences for all characters before processing the string.
📊
Partition Labels - Watch the Algorithm Execute, Step by Step
Watching each pointer move and comparison live reveals how the greedy approach ensures each letter belongs to exactly one partition, which is hard to grasp from code alone.
Step 1/18
·Active fill★Answer cell
setup
a
0
b
1
a
2
b
3
c
4
b
5
a
6
c
7
a
8
d
9
e
10
f
11
e
12
g
13
d
14
e
15
h
16
i
17
j
18
h
19
k
20
l
21
i
22
j
23
Result: []
fill_row
a
0
b
1
a
2
b
3
c
4
b
5
a
6
c
7
i
a
8
d
9
e
10
f
11
e
12
g
13
d
14
e
15
h
16
i
17
j
18
h
19
k
20
l
21
i
22
j
23
Result: []
fill_row
a
0
b
1
a
2
b
3
c
4
i
b
5
a
6
c
7
a
8
d
9
e
10
f
11
e
12
g
13
d
14
e
15
h
16
i
17
j
18
h
19
k
20
l
21
i
22
j
23
Result: []
fill_row
a
0
b
1
a
2
b
3
c
4
b
5
a
6
i
c
7
a
8
d
9
e
10
f
11
e
12
g
13
d
14
e
15
h
16
i
17
j
18
h
19
k
20
l
21
i
22
j
23
Result: []
fill_row
a
0
b
1
a
2
b
3
c
4
b
5
a
6
c
7
a
8
d
9
e
10
f
11
e
12
g
13
i
d
14
e
15
h
16
i
17
j
18
h
19
k
20
l
21
i
22
j
23
Result: []
fill_row
a
0
b
1
a
2
b
3
c
4
b
5
a
6
c
7
a
8
d
9
e
10
f
11
e
12
g
13
d
14
i
e
15
h
16
i
17
j
18
h
19
k
20
l
21
i
22
j
23
Result: []
setup
end
a
0
b
1
a
2
b
3
c
4
b
5
a
6
c
7
a
8
d
9
e
10
f
11
e
12
g
13
d
14
e
15
h
16
i
17
j
18
h
19
k
20
l
21
i
22
j
23
Result: []
move_right
start
a
0
b
1
a
2
b
3
c
4
b
5
a
6
c
7
end
a
8
d
9
e
10
f
11
e
12
g
13
d
14
e
15
h
16
i
17
j
18
h
19
k
20
l
21
i
22
j
23
Result: []
compare
start
a
0
i
b
1
a
2
b
3
c
4
b
5
a
6
c
7
end
a
8
d
9
e
10
f
11
e
12
g
13
d
14
e
15
h
16
i
17
j
18
h
19
k
20
l
21
i
22
j
23
Result: []
compare
start
a
0
b
1
a
2
b
3
i
c
4
b
5
a
6
c
7
end
a
8
d
9
e
10
f
11
e
12
g
13
d
14
e
15
h
16
i
17
j
18
h
19
k
20
l
21
i
22
j
23
Result: []
record
a
0
b
1
a
2
b
3
c
4
b
5
a
6
c
7
end
a
8
start
d
9
e
10
f
11
e
12
g
13
d
14
e
15
h
16
i
17
j
18
h
19
k
20
l
21
i
22
j
23
Result: [9]
move_right
a
0
b
1
a
2
b
3
c
4
b
5
a
6
c
7
a
8
start
d
9
e
10
f
11
e
12
g
13
end
d
14
e
15
h
16
i
17
j
18
h
19
k
20
l
21
i
22
j
23
Result: [9]
compare
a
0
b
1
a
2
b
3
c
4
b
5
a
6
c
7
a
8
start
d
9
e
10
f
11
e
12
i
g
13
end
d
14
e
15
h
16
i
17
j
18
h
19
k
20
l
21
i
22
j
23
Result: [9]
record
a
0
b
1
a
2
b
3
c
4
b
5
a
6
c
7
a
8
d
9
e
10
f
11
e
12
g
13
end
d
14
start
e
15
h
16
i
17
j
18
h
19
k
20
l
21
i
22
j
23
Result: [9,6]
move_right
a
0
b
1
a
2
b
3
c
4
b
5
a
6
c
7
a
8
d
9
e
10
f
11
e
12
g
13
d
14
end
e
15
h
16
i
17
j
18
h
19
k
20
l
21
i
22
j
23
Result: [9,6]
move_right
a
0
b
1
a
2
b
3
c
4
b
5
a
6
c
7
a
8
d
9
e
10
f
11
e
12
g
13
d
14
start
e
15
h
16
i
17
j
18
end
h
19
k
20
l
21
i
22
j
23
Result: [9,6]
record
a
0
b
1
a
2
b
3
c
4
b
5
a
6
c
7
a
8
d
9
e
10
f
11
e
12
g
13
d
14
e
15
h
16
i
17
j
18
h
19
k
20
l
21
i
22
end
j
23
Result: [9,6,9]
prune
a
0
b
1
a
2
b
3
c
4
b
5
a
6
c
7
a
8
d
9
e
10
f
11
e
12
g
13
d
14
e
15
h
16
i
17
j
18
h
19
k
20
l
21
i
22
j
23
Result: [9,7,8]

Key Takeaways

✓ The greedy approach extends the partition end to the farthest last occurrence of any character seen so far.

This insight is hard to see from code alone because it requires understanding how overlapping character occurrences affect partition boundaries.

✓ Partitions close exactly when the current index reaches the partition end, ensuring no character crosses partitions.

Visualizing pointer movements clarifies why this condition guarantees valid partitions.

✓ The last occurrence array is essential to quickly determine how far to extend partitions.

Seeing the last array filled step-by-step reveals its critical role in the algorithm.

Practice

(1/5)
1. Given the following code and input, what is the final returned total cost? 
def twoCitySchedCost(costs):
    costs.sort(key=lambda x: x[0] - x[1])
    n = len(costs) // 2
    total = 0
    for i, cost in enumerate(costs):
        if i < n:
            total += cost[0]
        else:
            total += cost[1]
    return total

costs = [[10,20],[30,200],[400,50],[30,20]]
print(twoCitySchedCost(costs))
easy
A. 110
B. 150
C. 120
D. 140

Solution

  1. Step 1: Sort costs by difference cost[0] - cost[1]

    Differences: [10-20=-10, 30-200=-170, 400-50=350, 30-20=10]. Sorted: [[30,200], [10,20], [30,20], [400,50]]

  2. Step 2: Assign first half to city A, rest to city B and sum costs

    First two: city A costs = 30 + 10 = 40; last two: city B costs = 20 + 50 = 70; total = 40 + 70 = 110

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    Sum matches manual calculation [OK]
Hint: Sort by difference, assign first half to city A [OK]
Common Mistakes:
  • Misordering after sorting by difference
  • Off-by-one in loop boundary
  • Adding wrong city cost for last half
2. Consider the following buggy code for candy distribution. Which line contains the subtle bug that can cause incorrect candy counts?
medium
A. Line 3: candies initialized with zeros instead of ones
B. Line 5: loop starts from 1 instead of 0
C. Line 7: candies[i] updated without checking if greater than candies[i-1]
D. Line 9: condition candies[i] <= candies[i + 1] missing

Solution

  1. Step 1: Check initialization of candies array

    Line 3 initializes candies with zeros, violating the problem requirement that each child must have at least one candy.

  2. Step 2: Understand impact of zero initialization

    Zero candies can cause incorrect comparisons and final sums, failing test cases where minimum is 1 per child.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Initialization must be at least 1 per child [OK]
Hint: Candies must start at 1, not 0 [OK]
Common Mistakes:
  • Forgetting minimum candy per child
  • Incorrect loop boundaries
  • Missing update conditions
3. The following code attempts to compute the minimum number of platforms needed. Identify the line containing the subtle bug that can cause incorrect platform count when a train arrives exactly at the departure time of another train.
medium
A. Line with 'while heap and heap[0] < arrival:'
B. Line with 'trains = sorted(zip(arrivals, departures), key=lambda x: x[0])'
C. Line with 'heapq.heappush(heap, departure)'
D. Line with 'max_platforms = max(max_platforms, len(heap))'

Solution

  1. Step 1: Understand the bug

    The condition 'heap[0] < arrival' pops platforms only if departure is strictly less than arrival, missing the case when departure == arrival.

  2. Step 2: Correct condition

    Changing condition to 'heap[0] <= arrival' correctly frees platforms when a train arrives exactly at departure time, avoiding overcounting.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Condition must include equality to avoid platform overcount [OK]
Hint: Use <= to free platform when arrival equals departure [OK]
Common Mistakes:
  • Using < instead of <= in heap pop condition
  • Not sorting trains by arrival time
  • Forgetting to update max_platforms
4. Suppose now each cookie can be assigned to multiple children (reusable cookies). Which modification to the original greedy algorithm correctly computes the maximum number of content children?
hard
A. Sort both arrays and increment both pointers i and j on assignment as before
B. Use the brute force nested loops approach to try all assignments since greedy fails with reusable cookies
C. Sort greed array only and assign the largest cookie to each child without sorting cookies
D. Keep sorting arrays, but do not increment cookie pointer j when a cookie is assigned; only increment child pointer i

Solution

  1. Step 1: Understand reuse effect

    Cookies can be assigned multiple times, so cookie pointer j should not advance on assignment.

  2. Step 2: Modify greedy accordingly

    Keep sorting both arrays, but only increment child pointer i when a cookie satisfies a child; j stays to reuse the same cookie.

  3. Final Answer:

    Option D -> Option D

  4. Quick Check:

    Not incrementing j allows cookie reuse [OK]
Hint: Do not advance cookie pointer on assignment for reuse [OK]
Common Mistakes:
  • Incrementing both pointers breaks reuse
  • Using brute force unnecessarily
  • Ignoring sorting leads to suboptimal matches
5. Suppose the problem is changed so that some people can be assigned to either city multiple times (reusable assignments), or the number of people sent to each city is not fixed. Which approach correctly adapts the solution?
hard
A. Use a dynamic programming approach to handle variable counts and reuse assignments
B. Use the same greedy sorting by cost difference and assign exactly n people to each city
C. Sort by absolute cost to city A and assign all to city A to minimize cost
D. Assign people greedily without sorting, picking the cheaper city for each person

Solution

  1. Step 1: Understand problem change

    Allowing reuse or variable counts breaks the fixed half assignment constraint, invalidating the greedy approach.

  2. Step 2: Why DP is needed

    Dynamic programming can explore all valid assignments with reuse or variable counts, ensuring minimal total cost under new constraints.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Greedy fails when constraints are relaxed; DP handles complex state space [OK]
Hint: Relaxed constraints require DP, not greedy [OK]
Common Mistakes:
  • Applying greedy unchanged despite constraint changes
  • Ignoring reuse possibility in assignment
  • Assuming sorting by absolute cost suffices