Editor

Where Does It Go?

#594 · Sorting and searching · Intermediate · Find and fix · 65 XP · about 9 min

insert_position(nums, target) takes a list sorted from smallest to largest and returns the index where target should be inserted to keep the list sorted. If target is already in the list, return the index of its first appearance. It uses binary search, so it stays fast on long lists.

The code in the editor has a bug. It works for values that belong inside the list, but insert_position([1, 3, 5], 9) gives 2 instead of 3.

Examples

insert_position([1, 3, 5, 7], 4)  # returns 2
insert_position([1, 3, 5], 9)     # returns 3
insert_position([1, 3, 5], 0)     # returns 0
insert_position([2, 2, 2], 2)     # returns 0

In the first example 4 goes between 3 and 5, at index 2.

Constraints

  • nums has 0 to 100,000 numbers, sorted from smallest to largest.

Fastest solvers

Leaderboard

First solves only, ranked by stars and then time.