grid47 Exploring patterns and algorithms
Nov 3, 2024
6 min read
Solution to LeetCode 35: Search Insert Position Problem
Given a sorted array of distinct integers and a target value, return the index of the target if it is present. If the target is not in the array, return the index where it should be inserted to maintain the sorted order.
Problem
Approach
Steps
Complexity
Input: A sorted array of distinct integers and a target value.
• Explanation: The target is not found, but it should be inserted at index 4 to keep the array sorted.
Approach: Use binary search to find the target's position or determine where it should be inserted in the sorted array.
Observations:
• The problem can be solved efficiently with a binary search approach due to the sorted nature of the array.
• Binary search ensures an O(log n) runtime, which is optimal for this problem.
Steps:
• Initialize left and right pointers.
• Iterate using a binary search approach, adjusting the pointers based on the comparison with the target value.
• Return the position of the target or where the target should be inserted.
Empty Inputs:
• The array may not be empty as per constraints.
Large Inputs:
• Test with large arrays to ensure the O(log n) time complexity holds.
Special Values:
• Test with a target value that is smaller or larger than all elements in the array.
Constraints:
• Handle edge cases where the target is at the start or end of the array.
intsearchInsert(vector<int>& nums, int target) {
int l =0, r = nums.size() -1;
while(l <= r) {
int mid = l + (r - l) /2;
if(nums[mid] == target) return mid;
if(nums[mid] < target) l = mid +1;
else r = mid -1;
}
return l;
}
1 : Function Declaration
intsearchInsert(vector<int>& nums, int target) {
This line declares a function named 'searchInsert' that takes a sorted array 'nums' and a target integer 'target' as input and returns the index where the target should be inserted.
2 : Variable Initialization
int l =0, r = nums.size() -1;
This line initializes two pointers, 'l' and 'r', to represent the left and right boundaries of the search range. 'l' is initialized to 0 (the start of the array), and 'r' is initialized to the index of the last element in the array.
3 : Loop Iteration
while(l <= r) {
This line starts a `while` loop that continues as long as the left pointer 'l' is less than or equal to the right pointer 'r'.
4 : Calculation
int mid = l + (r - l) /2;
This line calculates the middle index 'mid' using a formula that avoids integer overflow for large values of 'l' and 'r'.
5 : Conditional Check
if(nums[mid] == target) return mid;
This line checks if the element at the middle index 'mid' is equal to the target. If so, the function returns the index 'mid' as the target is already present in the array.
6 : Conditional Check and Index Update
if(nums[mid] < target) l = mid +1;
This line checks if the element at the middle index 'mid' is less than the target. If so, it means the target should be inserted after the middle element, so the left pointer 'l' is updated to 'mid + 1'.
7 : Conditional Check and Index Update
else r = mid -1;
If the element at the middle index 'mid' is greater than the target, it means the target should be inserted before the middle element, so the right pointer 'r' is updated to 'mid - 1'.
8 : Return
return l;
After the loop terminates, the left pointer 'l' will be pointing to the correct insertion index for the target element. The function returns 'l' as the result.
Best Case: O(log n)
Average Case: O(log n)
Worst Case: O(log n)
Description: The time complexity is O(log n) because binary search is performed on the sorted array.
Best Case: O(1)
Worst Case: O(1)
Description: The space complexity is O(1) as no additional space is used beyond the input array.
