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 :)
=================================================================
INSTAGRAM: / surya.pratap.k
LinkedIn: / surya-pratap-kahar-47b...
=================================================================
CODE LINK: gist.github.co...

[@manmeetsingh8349]

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

[@chetanmuliya6030]

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.

[@techdose4u]

Welcome :)

[@anirudh8575]

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 targetnums[len(nums)-1]: return len(nums)

[@abhishekverma7604]

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

[@avadheshsingh4255]

sir actually we need to apply this condition in order to know the correct position of the element to be inserted ->>>> return nums[low]

[@ayeshaadhikari6123]

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

[@vishalakkalkote1344]

class Solution { public int searchInsert(int[] nums, int target) { int start = 0; int end = nums.length - 1; while(start target) { return start; } else { start ++;} if(nums[end] < target) { return end + 1;} else {end --;} } return start; } }

[@quandingleberry445]

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; } }

[@agileprogramming7463]

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.

[@techdose4u]

😂 You are overestimating man 😅

[@agileprogramming7463]

@@techdose4u No sir I remember we had 6k subs in April challenge. Now more and more people are doing June challenge, also placement preparation is in full swing, if anyone comes across this channel they don't need to go anywhere else for placement prep once they see the videos here. I firmly believe by July end we will have 50k!!

[@mohammedfalih8713]

his great efforts truly deserve ... i hope he will reach it someday soon

[@jobanpreetsingh2370]

@@agileprogramming7463 and now it's 95k

[@Amit.01]

@@jobanpreetsingh2370 and now it's 153k

[@antonios-m4291]

class Solution { public: int searchInsert(vector& 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

[@hackytech7494]

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

[@techdose4u]

Welcome

[@md_aaqil8027]

Java Solution class Solution { public int searchInsert(int[] nums, int target) { int s=0; int e=nums.length; while(s

[@martandkaushik7468]

thanks bro

[@techdose4u]

Welcome :)

[@yitingg7942]

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

[@techdose4u]

Binary search is pretty hard you know. You need to try out the possible cases yourself. You can't really be sure all variants of problem 😅

[@yitingg7942]

@@techdose4u So I do need to try out all the possible cases? There is not magic formula that can handle almost everything and I just write it with my eyes closed ? lol I thought everybody is saying it's so easy.

[@harshitmalhotra8627]

Read the leetcode card of binary search. It has great explanation on what you are seeking.

[@asanitian6218]

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

[@techdose4u]

👍

[@seal0118]

i completely understand, but why does the correct index has to be "l" or "start" instead of "end" or "h", why is "l" always the correct index ? does it have to do with the nature of the array itself ?

[@akshatbhandari7237]

perfect

[@ManishaKumari-wi6kg]

Sir can u make a video on sort element based on frequency just I am not able to understand this after viewing code on gfg it used map, pair, vector......

[@techdose4u]

I have already used this technique in many of my videos. But I will still make it in future. I used to have this problem for a long time when I was a beginner myself 😅 So I can understand it well.I will add it to todo list.

[@ManishaKumari-wi6kg]

@@techdose4u ok

[@twbouji7580]

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.

[@arjunrai8126]

The thing is that h and l being integers h+l can sometimes exceed the integer limit which is 2power 32 -1. So to avoid that extreme case of overflow we generally use h + (h-l)/2 which is the equivalent of (h+l)/2

[@shreyamatade409]

Sometimes while coding on leetcode i get an error like "non void function doesn't return a value for all control paths". Can anyone tell me why does this happen?

[@techdose4u]

You need to have return statement outside of all if-else etc statements.

[@shreyamatade409]

@@techdose4u thanks a lot

[@techtransformers7464]

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

[@techdose4u]

Once the challenges are over I can :)

[@pratikshah9219]

this solution does not give a correct ans to [1,3] 3

[@murtaza4989726]

Why is no one interested in understanding why is 'low' always pointing to the index where the missing target should be inserted? Thanks alot for the explanation but it feels like feeding fish to the hungry and not actually teaching the hungry to catch fish.

[@techdose4u]

👍🏼

[@bhupeshbhatt4849]

Yes brother, I was searching for the same , I was returning max(low, end) and this is actually working. I want to know why returning "low" is working

[@vinaychowdary7693]

Can u make videos on concepts of data structures and algorithms

[@techdose4u]

Can you please elaborate. I will continue with only Data structure after this June challenge.

[@vinaychowdary7693]

@@techdose4u in this session mainly concentration on coding pblms, before going to coding we should know the concepts of data structures, algorithms and dynamic programming

[@safalyaghoshroy2405]

First viewer😁😁😁

[@techdose4u]

😁

[@tanishqgupta1071]

Nice explanation

[@techdose4u]

Thanks :)

[@anitasrivastava983]

Hello bhaiya! Is competitive programming necessary for interviews as there are some people who say that interviews 'won't be cracked' without CP , or leetcode is sufficient?

[@arunraju9705]

Yes it is necessary, interview paradigm is constantly changing, today's methods are not used for tomorrow, why not just focus on something that you are very uncomfortable at ?

[@techdose4u]

CP is good to improve your problem solving ability and keep you thinking like a programmer. When a new problem comes then CP guys have higher chance of solving it. But current placement scenario for most companies (apart from a handful like Codenation), you will be asked from questions on geeksforgeeks and leetcode. So if you focus on just leetcode itself, you will be very good and can crack any company interview. Many think that CP is the way, but CP is a way to improve problem solving ability but Leetcode is also very good alternative which is more placement oriented. Most of the CP concepts will never be asked in most of the placements. So, my advice is, do CP if you LOVE it and can give your good amount of time for it otherwise there is no point in doing CP for some time. You can improve on interview preparation in just a couple of months but CP requires much more time and dedication. So, it varies from person to person. But if you have an year and less then obviously go for Leetcode. I hope I answered your question.

[@Ck-ir8ts]

@@techdose4u you are doing great, people need mentors like you.

[@anitasrivastava983]

Thank you bhaiya!!! You are doing a fantastic job, your videos are gonna blow up soon or later.

[@farheenfirdous6530]

@@techdose4u thanks for the answer

[@ROHITKUMAR-pn4gj]

My question is why low index is alway going to correct position whats the logic behind this If anybody can help that would be a great😊

[@learnenjoyandgrow6601]

Loved it

[@techdose4u]

Thanks :)

[@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; }

[@caminante4222]

Why is l always at the correct position?

[@sameer23377]

Thanks bade bhai ,thoda sa hindi bhi bol diya kare🙂

[@techdose4u]

Can't do it :)

[@aaqibhamdule73]

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 if(nums[start]target){ 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; }

[@ImranAhmed-wd5tr]

Please share the software name that you use to write using pen tablet?

[@HimanshuSingh-ob9qo]

👍

[@techdose4u]

👍

[@Rizz_trader]

so confusing for me as a beginner

[@khokamohsin9307]

Can anyone give the c source file code for this program?

[@kyeiiih4422]

Great explanations. I have solved the same problem using 3 languages Java: class Solution { public int searchInsert(int[] nums, int target) { int start = 0; int end = nums.length - 1; //traverse through the array while (start nums[mid]) { start = mid + 1; } else if (target < nums[mid]) { end = mid - 1; } else { return mid; } } //return insert position return start; } } JavaScript: var searchInsert = function(nums, target) { let start = 0; let end = nums.length - 1; while(start nums[mid]) { start = mid + 1; } else if (target < nums[mid]) { end = mid - 1; } else { return mid; } } return start; }; Python 3: class Solution: def searchInsert(self, nums: List[int], target: int) -> int: l, r = 0, len(nums) - 1 while l nums[mid]: l = mid + 1 if target < nums[mid]: r = mid - 1 if target == nums[mid]: return mid return l Hope it helps someone