Jobs

Interviews

Discussions

Search Insert Position

Easy

Asked by:

13 views

Topics:

ArraysBinary Search

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 <= 10⁴
-10⁴ <= nums[i] <= 10⁴
nums contains distinct values sorted in ascending order.
-10⁴ <= target <= 10⁴

Try coding it in LeetCode

Search Insert Position

Easy

Asked by:

13 views

Topics:

ArraysBinary Search

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 <= 10⁴
-10⁴ <= nums[i] <= 10⁴
nums contains distinct values sorted in ascending order.
-10⁴ <= target <= 10⁴

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the expected range of values in the `nums` array and the `target`?
Can the input array `nums` be empty or null?
If the `target` is smaller than all elements in `nums`, should I return 0?
Is the input array guaranteed to be sorted in ascending order?
Can I assume the `nums` array contains only distinct integers, as stated in the problem description?

Brute Force Solution

Approach

Imagine you are looking for a specific page in a book where the pages are already sorted in ascending order. The brute force approach would mean going through each page, one by one, until you either find the exact page or find where it should be if it were present.

Here's how the algorithm would work step-by-step:

Start with the very first page in the book.
Check if the page you are looking for is the same as this page.
If it is, then you've found it, and you're done.
If not, check if the page you are looking for should come before this page. If so, you know where to put it.
If the page you're looking for should come after, move to the next page in the book.
Keep checking each page, one by one, in the same way.
If you get to the end of the book without finding the exact page, the place where the page would go is right after the last page.

Code Implementation

def search_insert_position_brute_force(sorted_numbers, target_number): 
    for index in range(len(sorted_numbers)): 
        # Check if the current number is equal to the target. 
        if sorted_numbers[index] == target_number: 
            return index

        # Check if the target should be inserted before the current number
        if sorted_numbers[index] > target_number:

            return index

    # If target is greater than all numbers, insert at the end
    return len(sorted_numbers)

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the sorted array of size n at most once. In the worst-case scenario, the target is greater than all elements in the array, and the algorithm must traverse the entire array to determine the insert position. Therefore, the time complexity is directly proportional to the size of the input array, resulting in O(n) time complexity.

Space Complexity

O(1) – The algorithm iterates through the input sequentially, comparing the target value with each element. It does not use any additional data structures like lists, hash maps, or sets to store intermediate results. The algorithm only uses a fixed number of variables for comparisons and indexing, irrespective of the input size (N, the number of pages). Therefore, the space complexity is constant.

Optimal Solution

Approach

The efficient way to solve this is to repeatedly cut the search area in half. We use the sorted nature of the input to quickly eliminate large sections, getting us to the right spot faster than checking each place individually.

Here's how the algorithm would work step-by-step:

Start by looking at the middle number of the range.
If the middle number is bigger than the target number, you know the target belongs in the first half, so focus your attention on that first half.
If the middle number is smaller than the target, you know the target belongs in the second half, so look at that second half only.
Keep repeating this process of halving the search area until you find the target number, or the area is small enough that you find the spot where the target number would fit.

Code Implementation

def search_insert_position(number_array, target_value):
    left_index = 0
    right_index = len(number_array) - 1

    while left_index <= right_index:
        middle_index = (left_index + right_index) // 2
        middle_value = number_array[middle_index]

        # If the target is found, return the index.
        if middle_value == target_value:
            return middle_index

        # Adjust search range if target is smaller.
        if middle_value > target_value:

            right_index = middle_index - 1

        # Adjust search range if target is larger.
        else:

            left_index = middle_index + 1

    # If target is not found, return insertion index.
    # Left index is where the element should be inserted.
    return left_index

Big(O) Analysis

Time Complexity

O(log n) – The algorithm uses binary search, repeatedly halving the search interval. In each step, the algorithm compares the target value with the middle element of the current interval. Based on the comparison, the algorithm either finds the target or reduces the interval to half its size. The number of times the interval can be halved until it becomes of size 1 is logarithmic with respect to the input size n. Therefore, the time complexity is O(log n).

Space Complexity

O(1) – The binary search algorithm, as described, uses only a few variables to keep track of the low and high indices of the search range. These variables consume a constant amount of space regardless of the size of the input array, denoted as N. The halving process does not create any additional data structures or copies of the array, meaning the memory overhead is independent of the input size. Therefore, the space complexity is O(1).

Edge Cases

Case	How to Handle
Empty input array (nums is null or has length 0)	Return 0 since the target would be inserted at the beginning.
Target is smaller than the first element in nums	Return 0 as the target belongs at the beginning of the array.
Target is larger than the last element in nums	Return nums.length as the target belongs at the end of the array.
nums contains a single element and target is equal to it	Return 0, the index of the single element.
Large input array to ensure binary search scales efficiently	Use binary search algorithm for logarithmic time complexity O(log n).
Integer overflow when calculating mid in binary search (especially in languages like Java/C++)	Use mid = low + (high - low) / 2 to prevent overflow instead of mid = (low + high) / 2.
Array contains very large numbers that could cause overflow when target is added to an element	The comparison-based approach of binary search avoids summing array elements with the target so no overflow happens.
Target is present in the array.	The binary search should return the index of the existing element.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the expected range of values in the `nums` array and the `target`?
Can the input array `nums` be empty or null?
If the `target` is smaller than all elements in `nums`, should I return 0?
Is the input array guaranteed to be sorted in ascending order?
Can I assume the `nums` array contains only distinct integers, as stated in the problem description?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start with the very first page in the book.
Check if the page you are looking for is the same as this page.
If it is, then you've found it, and you're done.
If not, check if the page you are looking for should come before this page. If so, you know where to put it.
If the page you're looking for should come after, move to the next page in the book.
Keep checking each page, one by one, in the same way.
If you get to the end of the book without finding the exact page, the place where the page would go is right after the last page.

Code Implementation

def search_insert_position_brute_force(sorted_numbers, target_number): 
    for index in range(len(sorted_numbers)): 
        # Check if the current number is equal to the target. 
        if sorted_numbers[index] == target_number: 
            return index

        # Check if the target should be inserted before the current number
        if sorted_numbers[index] > target_number:

            return index

    # If target is greater than all numbers, insert at the end
    return len(sorted_numbers)

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Start by looking at the middle number of the range.
If the middle number is bigger than the target number, you know the target belongs in the first half, so focus your attention on that first half.
If the middle number is smaller than the target, you know the target belongs in the second half, so look at that second half only.
Keep repeating this process of halving the search area until you find the target number, or the area is small enough that you find the spot where the target number would fit.

Code Implementation

def search_insert_position(number_array, target_value):
    left_index = 0
    right_index = len(number_array) - 1

    while left_index <= right_index:
        middle_index = (left_index + right_index) // 2
        middle_value = number_array[middle_index]

        # If the target is found, return the index.
        if middle_value == target_value:
            return middle_index

        # Adjust search range if target is smaller.
        if middle_value > target_value:

            right_index = middle_index - 1

        # Adjust search range if target is larger.
        else:

            left_index = middle_index + 1

    # If target is not found, return insertion index.
    # Left index is where the element should be inserted.
    return left_index

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty input array (nums is null or has length 0)	Return 0 since the target would be inserted at the beginning.
Target is smaller than the first element in nums	Return 0 as the target belongs at the beginning of the array.
Target is larger than the last element in nums	Return nums.length as the target belongs at the end of the array.
nums contains a single element and target is equal to it	Return 0, the index of the single element.
Large input array to ensure binary search scales efficiently	Use binary search algorithm for logarithmic time complexity O(log n).
Integer overflow when calculating mid in binary search (especially in languages like Java/C++)	Use mid = low + (high - low) / 2 to prevent overflow instead of mid = (low + high) / 2.
Array contains very large numbers that could cause overflow when target is added to an element	The comparison-based approach of binary search avoids summing array elements with the target so no overflow happens.
Target is present in the array.	The binary search should return the index of the existing element.