35. Search Insert Position
Search Insert Position (LeetCode 35) is a Easy Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Binary Search Patterns pattern, in the On Sorted Array/List subpattern.
How to solve Search Insert Position
Search Insert Position is a Binary Search on Sorted Array problem, part of Binary Search Patterns. Master standard binary search on sorted arrays. Learn search insert position, sqrt calculation, and 2D matrix search.
Work towards the solution in these steps:
- Since the input array is sorted and you need to find the target or its insertion position efficiently, consider which search algorithm suits this scenario.
- Binary search is ideal for searching in sorted arrays with O(log n) time complexity; think about how to apply it here.
- During binary search, if you do not find the target, the pointers will cross; analyze how the pointers' positions at this point can determine the insertion index.
The reference solution runs in O(logn) time and O(1) space.
The Search Insert Position solution and editorial walks through the full approach with reference code.
Problem statement
Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.
You must write an algorithm with O(log n) runtime complexity.
Example 1:
Input: nums = [1,3,5,6], target = 5 Output: 2
Example 2:
Input: nums = [1,3,5,6], target = 2 Output: 1
Example 3:
Input: nums = [1,3,5,6], target = 7 Output: 4
Constraints:
- 1 <= nums.length <= 104
- -104 <= nums[i] <= 104
- nums contains distinct values sorted in ascending order.
- -104 <= target <= 104
Topics and companies
Topics: Array, Binary Search.
Reported in interviews at Apple, Amazon.
How to practise Search Insert Position on Thita.ai
Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(logn) time and O(1) space.
Open Search Insert Position in the code editor, or read the Search Insert Position editorial for a worked solution with its approach and complexity analysis.
Where Search Insert Position sits in the DSA pattern sheet
Problems related to Search Insert Position
Other problems that use the same On Sorted Array/List and Binary Search Patterns techniques:
- Binary Search — Easy, same subpattern
- First Bad Version — Easy, same subpattern
- Guess Number Higher or Lower — Easy, same subpattern
- Kth Missing Positive Number — Easy, same subpattern
- Search a 2D Matrix — Medium, same subpattern
- Single Element in a Sorted Array — Medium, same subpattern
Search Insert Position FAQ
What is the LeetCode number of Search Insert Position?
Search Insert Position is LeetCode problem 35, rated Easy.
What pattern is used to solve Search Insert Position?
Search Insert Position is a Binary Search on Sorted Array problem. It belongs to the Binary Search Patterns pattern, in the On Sorted Array/List subpattern.
What is the time complexity of Search Insert Position?
The reference solution runs in O(logn) time and O(1) space.
Which companies ask Search Insert Position?
Search Insert Position has been reported in interviews at Apple, Amazon.