Insert into Sorted Array

1. Define the problem

Given an integer array nums sorted in non-decreasing order and an integer target, insert target into nums so the array stays sorted in non-decreasing order , then return the resulting array. Use the shift-and-insert mechanic: scan from the right, shifting every value bigger than target one slot right, then drop target into the gap.

Constraints

0 ≤ nums.length ≤ 100
-1000 ≤ nums_i, target ≤ 1000

Example

Inputnums = [1, 3, 4, 7], target = 5

Output[1, 3, 4, 5, 7]

Explanation 7 is bigger than 5, so it shifts right one slot, and 5 drops into the gap it leaves behind.

2. Know the words first

In plain terms

Non-decreasing order: Each value is greater than or equal to the one before it, so repeats are allowed — for example, [1, 2, 2, 5] is in non-decreasing order.
Shift: Moving a bigger value one slot to the right to make room for the value being inserted.

3. Visualize the solution

Shift larger values right, drop the target into the gap

Statusinit

target = 5 sits after the sorted prefix [1, 3, 4, 7]. Compare it against 7.

What happens in this step

result = [1, 3, 4, 7, 5]
i = 3 → result[3] = 7

target = 5 is appended at the end; i starts at the last real index (3), pointing at 7, ready to compare.

Step 1 of 4

Steps to visualize

Place target at the end of the array, right after the sorted prefix.
Compare target against the value to its left.
While that value is bigger than target, shift it one slot right and step left.
Stop the moment you find a smaller value or reach the start of the array.
Write target into the gap that was left behind.

4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Shift larger values right, drop the target into the gap

Statusinit

target = 5 sits after the sorted prefix [1, 3, 4, 7]. Compare it against 7.

What happens in this step

result = [1, 3, 4, 7, 5]
i = 3 → result[3] = 7

target = 5 is appended at the end; i starts at the last real index (3), pointing at 7, ready to compare.

Step 1 of 4

5. Solution

Solution

solution.tsTypeScript

function insertSorted(nums, target) {
  const result = nums.slice();
  result.push(target);
  let i = result.length - 2;

  while (i >= 0 && result[i] > target) {
    result[i + 1] = result[i];
    i--;
  }

  result[i + 1] = target;
  return result;
}

Time: O(n)
Space: O(n)

6. Test cases

Test cases

Input	Expected	Covers
`nums = [1, 3, 4, 7], target = 5`	`[1, 3, 4, 5, 7]`	example from the docstring
`nums = [5, 8, 10], target = 1`	`[1, 5, 8, 10]`	target is smaller than every existing value
`nums = [2, 4, 6], target = 9`	`[2, 4, 6, 9]`	target is bigger than every existing value, no shifting
`nums = [], target = 5`	`[5]`	inserting into an empty array
`nums = [2, 4, 4, 6], target = 4`	`[2, 4, 4, 4, 6]`	target ties with an existing value and lands after it
`nums = [10], target = 3`	`[3, 10]`	smallest non-trivial array, target smaller than the only value
`nums = [3], target = 10`	`[3, 10]`	smallest non-trivial array, target bigger than the only value

Insert into Sorted Array