Hacker News Reader

I don’t think I understand the problem. We have n distinct integers, and the array has already been partitioned. Why isn’t the answer just that there was exactly one pivot that could generate that partition?

View on HN

I didin't really understand it either. I think the problem is taking in an array that's already been partitioned around a pivot, and then trying to figure out how many numbers could have been the pivot. The reason why this isn't just the length of the array is because the array is already pivoted. The reason why you have to use a linear scan is because the array is still in unsorted order.

For [1, 2, 3, 4, 5] there are 5 pivots.

For [1, 2, 3, 5, 4] there are 3 pivots (1, 2, and 3)

For [2, 1, 3, 5, 4] there is only 1 (3).

That makes more sense. Thanks.

Take the trivial example where A is [1, 3, 2, 4]. We can pivot around 2 to get A' = [1, 2, 3, 4], but we can also pivot around 3 to get A' = [1, 2, 3, 4]. So given A', both 2 and 3 are valid pivots.

Edit: in fact, 1 and 4 may be valid pivots too for this example, if empty subarrays are allowed (remember that we don't necessarily know A, so A = [4, 1, 2, 3] with a pivot of 4 will yield the same A' = [1, 2, 3, 4], as will A = [2, 3, 4, 1] with a pivot of 1).

Reply on news.ycombinator.com