FastPrep
Problem · Array

Sorted Insertion Snapshots

Learn this problem
● MediumSquarepoint Capital logoSquarepoint CapitalFULLTIMEPHONE SCREEN

Problem statement

Process the integers in values from left to right while maintaining one sorted vector-like sequence. Insert each new value at its lower-bound position: immediately before the first current value that is greater than or equal to it.

Return one snapshot after every insertion. Snapshot i contains the complete sorted sequence after inserting values[i]. Insertion by move and insertion by copy have the same observable value behavior in this exercise.

Function

sortedInsertionSnapshots(values: int[]) → int[][]

Examples

Example 1

values = [3,1,2]return = [[3],[1,3],[1,2,3]]

Each row captures the full ordered sequence after that insertion.

Example 2

values = [2,2,-1]return = [[2],[2,2],[-1,2,2]]

Equal values remain adjacent and the final negative value moves to the front.

Example 3

values = [1,4,9]return = [[1],[1,4],[1,4,9]]

Every new value belongs at the end.

Constraints

  • 1 <= values.length <= 1000.
  • -10^9 <= values[i] <= 10^9.
  • The total number of returned integers is at most 500500.

More Squarepoint Capital problems

drafts saved locally
public int[][] sortedInsertionSnapshots(int[] values) {
  // write your code here
}
values[3,1,2]
expected[[3],[1,3],[1,2,3]]
checking account