🎨Now live: Try our Free AI Image Generation Feature

Description
The searchInsert
function finds the index at which a target value should be inserted into a sorted list nums
to maintain the order. If the target value is found in the list, the function returns the index of the target value.
Intuition
To determine the correct position for the target value, we need to traverse the list and compare each element with the target. By checking where the target fits within the existing elements, we can either find its position or determine where it should be inserted.
Approach
- Initialize Variables:
-
result
: Initialize to 0, this will store the index where the target should be inserted or found. - Iterate Through the List:
- Use a for loop to traverse the list from the end to the beginning.
- Compare each element with the target value:
- If the target is greater than the current element, set
result
to the next index (i + 1
) and break the loop. - If the target is equal to the current element, setresult
to the current index (i
) and break the loop. - Return Result:
- Return the value of
result
, which represents the correct index for the target value.
Complexity
Time Complexity:
O(n), where n is the number of elements in the list. We may need to traverse the entire list in the worst case.
Space Complexity:
O(1), as we only use a constant amount of extra space for the result
variable.
Code
C++
class Solution {
public:
int searchInsert(vector& nums, int target) {
int result = 0;
for (int i = nums.size() - 1; i >= 0; i--) {
if (target > nums[i]) {
result = i + 1;
break;
}
if (target == nums[i]) {
result = i;
break;
}
}
return result;
}
};
Python
class Solution:
def searchInsert(self, nums: List[int], target: int) -> int:
result = 0
for i in range(len(nums) - 1, -1, -1):
if target > nums[i]:
result = i + 1
break
if target == nums[i]:
result = i
break
return result
Java
class Solution {
public int searchInsert(int[] nums, int target) {
int result = 0;
for (int i = nums.length - 1; i >= 0; i--) {
if (target > nums[i]) {
result = i + 1;
break;
}
if (target == nums[i]) {
result = i;
break;
}
}
return result;
}
}
JavaScript
var searchInsert = function(nums, target)
{
let result = 0;
for(let i=nums.length-1; i>=0; i--)
{
if(target>nums[i])
{
result = i+1;
break;
}
if(target==nums[i])
{
result = i;
break;
}
}
return result;
};