[Interview Question] How To Search The Insert Position Of Target In A Sorted Array?

[toc]

Company tags: Adobe, Uber, Airbnb, Bloomberg

Are you looking to ace your coding interview? If yes! Then this question is one the must-do for you as it has been reportedly asked in numerous interviews by some of the giant organizations like Adobe. Can you solve this problem optimally?

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.

Challenge: Can you propose an algorithm with O(log n) runtime complexity?

⚠️Constraints:

1 <= nums.length <= 104
-10⁴ <= nums[i] <= 10⁴
nums contains distinct values sorted in “ascending order”.
-10⁴ <= target <= 10⁴

Examples

Let us look at some examples to improve the understanding of the problem:

Example 1:
Input:
nums = [1, 3, 5, 6]
target = 5
Output: 2
Explanation: Target 5 is indexed at position 2 in the array.

Example 2:
Input:
nums = [1, 3, 5, 6]
target = 2
Output: 1
Explanation: Target 2 will be inserted at position 1 in the array.

Example 3:
Input:
nums = [1, 3, 5, 6]
target = 7
Output: 4
Explanation: Target 7 will be inserted at position 4 in the array.

Example 4:
Input:
nums = [1, 3, 5, 6]
target = 0
Output: 0
Explanation: Target 0 will be inserted at position 0 in the array.

Example 5:
Input:
nums = [1]
target = 0
Output: 0
Explanation: Target 0 will be inserted at position 0 in the array.

Now that you have a clear understanding of the problem, let’s dive into various methods to solve the problem:

Method 1: Linear search

Approach: The most straightforward way to solve the problem would be to iterate through every number in the array. Return the index if the target gets found. Else, check where the target value could be inserted and return that index value.

Algorithm:

Check if the array is empty. If yes, return 0.
If the target value is greater than the last element in the array, then the target value would get inserted at the end of the array. Hence, return the length of the array.
If the target value is smaller than the first element in the array, the target would be inserted at the beginning of the array. Hence, return 0.
Further, traverse the array. If the current number is greater than or equal to the target value, return the current index.

Solution:

def search_insert(nums, target):
    if not nums:
        return 0
    if target > nums[-1]:
        return len(nums)
    if target < nums[0]:
        return 0
    for i in range(len(nums)):
        if nums[i] >= target:
            return i

Test Case Analysis:

Let’s run this solution on our examples:

# Example 1
nums = [1, 3, 5, 6]
target = 5
print(search_insert(nums, target))
# 2

# Example 2
nums = [1, 3, 5, 6]
target = 2
print(search_insert(nums, target))
# 1

# Example 3
nums = [1, 3, 5, 6]
target = 7
print(search_insert(nums, target))
# 4

# Example 4
nums = [1, 3, 5, 6]
target = 0
print(search_insert(nums, target))
# 0

# Example 5
nums = [1]
target = 0
print(search_insert(nums, target))
# 0

Yeah! It passed all the test cases.

Complexity Analysis:

Time Complexity: In the worst-case scenario, you have to visit every number in the array. Hence, the time complexity of this method is O(n).
Space Complexity: No extra space is used. Hence, the space complexity of this method is O(1).

Discussion: Though this algorithm fetches us the required output, however, it does not ensure that the runtime complexity is log(n) which is also a challenge presented to us. In the next approach, we will find out how to use binary search and reach the optimal solution.

Method 2: Binary search

Approach: A better approach would be to use binary search as you will be searching for a particular element in the array. You have to initialize two-pointers and calculate the value of mid. Compare the mid-value with the target value and return the index if found.

Algorithm:

Check if the array is empty. If yes, return 0.
Initialize the variables low and high with 0 and len(nums), respectively.
While the “low” index is less than “high”, calculate the mid-value.
Compare the mid-value with the target value.
If the target value is greater than the mid-value, then the target value will be to the right. Update low to mid + 1.
Else, if the target value is less than or equal to the mid-value, update high to mid.
When you exit the loop, the position of the low pointer is either at the position equal to the target value or at the position where you have to insert the target value. Thus, return the value pointed by low.

Consider the following illustration to understand the approach better:

Solution:

def search_insert(nums, target):
    if not nums:
        return 0
    low, high = 0, len(nums)
    while low < high:
        mid = (low + high) // 2
        if target > nums[mid]:
            low = mid + 1
        else:
            high = mid
    return low

Test Case Analysis:

Let’s run this solution on our examples:

Yeah! It passed all the test cases.

Complexity Analysis:

Time Complexity: As this method uses binary search, you have to traverse only half the array. Hence, the time complexity of this method is O(log(n)).
Space Complexity: No extra space is used. Hence, the space complexity of this method is O(1).

Do you want to develop the skills of a well-rounded Python professional—while getting paid in the process? Become a Python freelancer and order your book Leaving the Rat Race with Python on Amazon (Kindle/Print)!

Bonus Method: Using Bisect Module

Approach: You can use the Bisect module directly to find the position of the target element. The bisect_left method of the bisect module is used to find the index of the target element in the sorted array. If the element is already present in the array then the leftmost position where the element can be inserted within the list gets returned.

Bisect Module Recap:
➥ The purpose of the Bisect algorithms is to find the index/position of a required element within a given list where the element has to be inserted within the list. Therefore, it helps to keep the list sorted after the insertion is complete.
➥ bisect_left method of the bisect module is used to find the index of the target element in the sorted list. If the element is already present in the list then the leftmost position where the element can be inserted within the list is returned.

Solution:

from bisect import bisect_left


def search_insert(nums, target):
    return bisect_left(nums, target)

Test Case Analysis:

Let’s run this solution on our examples:

# Example 1
nums = [1, 3, 5, 6]
target = 5
print(search_insert(nums, target))
# 2

# Example 2
nums = [1, 3, 5, 6]
target = 2
print(search_insert(nums, target))
# 1

# Example 3
nums = [1, 3, 5, 6]
target = 7
print(search_insert(nums, target))
# 4

# Example 4
nums = [1, 3, 5, 6]
target = 0
print(search_insert(nums, target))
# 0

# Example 5
nums = [1]
target = 0
print(search_insert(nums, target))
# 0

Yeah! It passed all the test cases.

Complexity Analysis:

Time Complexity: As this method is similar to binary search, the time complexity of this method is O(log(n)).
Space Complexity: No extra space is used. Hence, the space complexity of this method is O(1).

Conclusion

I hope you enjoyed this coding interview question. Please stay tuned and subscribe for more interesting coding problems.

Post Credits: Shubham Sayon and Rashi Agarwal

Recommended: Finxter Computer Science Academy

One of the most sought-after skills on Fiverr and Upwork is web scraping. Make no mistake: extracting data programmatically from websites is a critical life skill in today’s world that’s shaped by the web and remote work.
So, do you want to master the art of web scraping using Python’s BeautifulSoup?
If the answer is yes – this course will take you from beginner to expert in Web Scraping.