Search Insert Position | Leetcode #35

This video explains a very basic programming interview question which is to find the correct position to insert an element in a already sorted array.All elements of array are sorted.The element may be already present in array and so we just need to return its index in this case.If element is not present then return the index where it can be inserted so that array remains in ascending order.This can be simply solved in linear time using linear search but since the array is sorted, we can apply binary search which will reduce time to logN.I have shown all possible cases with examples and the code walkthrough at the end of the video.CODE LINK is present below as usual. If you find any difficulty or have any query then do COMMENT below. PLEASE help our channel by SUBSCRIBING and LIKE our video if you found it helpful...CYA :)

=================================================================
=================================================================

[manmeetsingh]

class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
for (int i = 0; i < nums.size(); i++) {
if (target <= nums[i]) {
return i;
}
}
return nums.size();
}
};Ez

[chetanmuliya]

Consisteny is the key to get you anywhere you wish, and now i feel i am getting there thank you sir learn a lot from you Big hug.

[anirudh]

for i in range(len(nums)):
if nums[i]==target:
return i
if nums[i]>target:
# If nums[i] is greater, this means that target should be in nums[i]
return i
if target<nums[0]:
return 0
if target>nums[len(nums)-1]:
return len(nums)

[abhishekverma]

ultimately, in all cases we have to return low, which simultaneously cover all the corner cases..
great explanation sir...

[antonios-m]

class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
auto it = std::find(nums.begin(), nums.end(), target);
if(it == nums.end())
it = std::find_if(nums.begin(), nums.end(), [&](int num){ return num > target; });

return it - nums.begin();
}
};
using C++ find algorithms

[avadheshsingh]

sir actually we need to apply this condition in order to know the correct position of the element to be inserted ->>>>
return nums[low]<target ? low+1 : low;

[hackytech]

This was the best explanation for the solution as well as for binary search algorithm. Thank you so much

[asanitian]

Why mid=low+(high-low)/2, we can take it as mid=(low+high)/2

[evgeni-nabokov]

Rust has this function:
(match nums.binary_search(&target) {
Ok(i) => i,
Err(i) => i,
}) as i32

[vishalakkalkote]

class Solution {
public int searchInsert(int[] nums, int target) {
int start = 0;
int end = nums.length - 1;

while(start <= end) {
if(nums[start] == target) return start;
if(nums[end] == target) return end;

if(nums[start] > target) { return start; }
else { start ++;}

if(nums[end] < target) { return end + 1;}
else {end --;}
}

return start;
}
}

[ayeshaadhikari]

Thank you so much sir for helping so many of us with your knowledge! :)

[quandingleberry]

class Solution {
public int searchInsert(int[] nums, int target) {
if (target > nums[nums.length-1]) {
return nums.length;
}

if (target < nums[0]) {
return 0;
}

for (int i = 0; i < nums.length; i++) {
if (nums[i] == target) {
return i;
} else if (nums[i] < target && nums[i+1] > target) {
return i+1;
}
}
return 0;
}
}

[agileprogramming]

Thanks again for the explanation!

I just printed low and high at the end of loop for 5-6 test cases and saw that low is always pointing to the correct index. :)))

Also congo for 16k subs. Way to go! I think in about a month or so there will definitely be 50k subs or more.

[MGtvMusic]

Solution in C
int searchInsert(int* nums, int numsSize, int target){
int *Iter = nums;
int *End = nums + numsSize;

for (int I = 0; Iter != End; I++, Iter++) {
if (*Iter >= target) {
return I;
}
}

return numsSize;
}

[yitingg]

Thank you for the explanation. I understand the concept which is fairly simple. But I get so confused every time if I should use while(left < right) or while (left <= right) and also how to change the left and right pointer. Do you have any videos about how to handle the boundary and edge cases sir ?

[vinaychowdary]

Can u make videos on concepts of data structures and algorithms

[md_aaqil]

Java Solution
class Solution {
public int searchInsert(int[] nums, int target) {
int s=0;
int e=nums.length;
while(s<e)
{
int mid=s+(e-s)/2;
if(nums[mid]==target)
return mid;
else if(nums[mid]<=target)
s=mid+1;
else
e=mid;
}
return e;
}
}

[techtransformers]

can you please make a video on 763. partition labels - leet code

[twbouji]

Hello, thank you for the video!
Why mid = (l+h)/2 isn't enough? my guess is that by writing l+(h-l)/2 we reduce the boundary of the array that we already visited.

[aaqibhamdule]

This solution runs the fastest :
public int searchInsert(int[] nums, int target) {
int start = 0;
int end = nums.length-1;
int result = -1;
if(nums.length==1){
if(nums[0]>=target){
return 0;
}else{
return 1;
}
}
while(end >= start){
int midPoint = (start+end)/2;
if(end - start == 1){
if(nums[start]>=target){
result = start;
}
else
result = start+1;
}else if(nums[end]==target){
result = end;
}else{
result = end + 1;
}
break;
}
if(nums[midPoint]==target){
result = midPoint;
break;
}else if(nums[midPoint]>target){
end = midPoint;
}else {
start = midPoint;
}
result = midPoint;
}
return result;
}