algoadvance

Leetcode 35. Search Insert Position

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.

Clarifying Questions

  1. Q: Can the input array contain duplicate values?
    • A: No, the array contains distinct integers.
  2. Q: Is the array always sorted?
    • A: Yes, the array is always sorted.
  3. Q: Can the array be empty?
    • A: Yes, it can be empty, in which case we should return 0 since the target would be inserted at the beginning.
  4. Q: What should be the behavior if the target is less than all elements in the array?
    • A: The target should be inserted at the beginning (index 0).
  5. Q: What should be the behavior if the target is greater than all elements in the array?
    • A: The target should be inserted at the end (index equal to the length of the array).

Strategy

  1. Binary Search Approach:
    • Since the array is sorted and we need a runtime complexity of O(log n), a binary search is an ideal approach for this problem.
    • If the target is found during binary search, return the index.
    • If the target is not found, the binary search will converge to the point where the target should be inserted. The low pointer will indicate the correct insertion point by the end of the search.

Code

#include <vector>
#include <iostream>

class Solution {
public:
    int searchInsert(std::vector<int>& nums, int target) {
        int low = 0, high = nums.size() - 1;
        
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (nums[mid] == target)
                return mid;
            else if (nums[mid] < target)
                low = mid + 1;
            else
                high = mid - 1;
        }
        
        return low; // low is the insertion point
    }
};

int main() {
    Solution solution;
    std::vector<int> nums = {1, 3, 5, 6};
    int target = 5;
    std::cout << "Index: " << solution.searchInsert(nums, target) << std::endl; // Output: 2

    target = 2;
    std::cout << "Index: " << solution.searchInsert(nums, target) << std::endl; // Output: 1

    target = 7;
    std::cout << "Index: " << solution.searchInsert(nums, target) << std::endl; // Output: 4

    target = 0;
    std::cout << "Index: " << solution.searchInsert(nums, target) << std::endl; // Output: 0

    return 0;
}

Time Complexity

This implementation ensures that we efficiently find the correct target index or insertion point in logarithmic time.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI