3 ms·

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 exactl

• jonathankoren 8y ago
  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).
  • monochromatic 8y ago
    That makes more sense. Thanks.
• smaccona 8y ago
  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).
• deleted 8y ago
  [deleted]