Coding Interview Question | First, Last Position of Element in sorted array | Modified Binary Search

The video includes following details-
0:00-0:35 - Question Explanation
0:35-0:45 - Brute Force solution
0:45-1:35 - Binary search and how to use in this question
1:35-6:05 - First position algo
6:05-8:30 - First position dry run
8:30-10:35 - Last position algo
10:35-12:00 - Last position dry run

Fun and Artistic Stuff at-

[balajimysore]

Hi Keerti,
For input A = [2, 2] or A=[1] the condition which is used will fail. We need to change the logic a little bit if((mid == 0 || A[mid-1] < target) && A[mid] == target) should do the trick for 1st element, and if((mid == n-1 || A[mid+1] > target) && A[mid] == target) should do the trick for last element.
Explanation:
A[mid-1] < target && A[mid] == target : If the 1st occurrence is somewhere in the middle
mid == 0 && A[mid] == target : If the 1st occurrence is the 1st element in the array

A[mid+1]>target && A[mid] == target: If the last occurrence is somewhere in the middle
mid == n-1 && A[mid] == target: If the last occurrence is the last element in the array

Hope this helps people looking for the updated solution..

Otherwise very clear and concise explanation for the solution. Keep going Keerti.

[ScrolltheNature]

arr[mid-1]!=value this was simple condition to break this problem..thanks

[TarunKumar]

Hi Keerti, Thanks for explaining it very well. But I was running the same algo for input [1]. It was not working as expected. The reason is the boundary check that you have put here like m > 0 and m < n-1 were creating problem for me. I have removed that and now its working fine.

[nishkarshaggarwal]

Kaafi sare test cases fail ho jayenge aapke solution m
Jaise [2, 2] m agar hum 2 search kar rahe hai toh aapke program fail ho jayega

[1] pe bhi fail ho jayega..

[shashankdesai]

Thanks a lot for the clear explanation Ma'am.. After watching this video i regret for not watching your videos for all the other DSA concepts/problems...

[imranwahid]

Thank you so much, ma'am. Your way of explanation is really praiseworthy.

[MidhunDarvin]

Is the condition when the first occurrence of the element is at index 0 handled ? ( since we are always checking mid > 0 ) Similarly in the second algorithm, when we want to find out the last occurrence of the element is at the last index of the array.

[ayanchowdhury]

Really helpful content!please keep posting more..Thanks a lot

[royarijit]

Ma'am, can you do a video on 'median of 2 sorted array' (same and different sized arrays) next, please?
Your videos help a lot, thanks a lot for putting in so much effort!!

[Prashantkumar-rhni]

SO Niceely explained👌👍
Please make some videos on algorithm.

[gauravjha]

Python solution for the given algorithm

def FindFirstOccurence(nums, start, end, target):
first =-1
if nums[start] == target:
return start
while start <= end:
mid = start + (end-start)//2
if mid > 0 and nums[mid]==target and nums[mid-1] != target:
first = mid
break
elif nums[mid] >= target:
end = mid - 1
else:
start = mid + 1
return first
def FindLastOccurence(nums, start, end, target):
last =-1
if nums[end] == target:
return end
while start <= end:
mid = start +(end-start)//2
if mid < len(nums)-1 and nums[mid] == target and nums[mid+1] != target:
last = mid
break
elif nums[mid] <= target:
start = mid+1
else:
end = mid - 1
return last


class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
start =0
end = len(nums) - 1
l=[]
if len(nums) == 0:
return [-1, -1]
if len(nums) == 1 and nums[start] == target:
l.append(start)
l.append(start)
return l

firstOccurence = FindFirstOccurence(nums, start, end, target)
lastOccurence = FindLastOccurence(nums, start, end, target)
l.append(firstOccurence)
l.append(lastOccurence)
return l

[jeevapriya]

Mam plz make more videos on leetcode solutions by topic wise like arrays, strings,linked lists .... ur explanation was damn clr .... keep going mam

[tayyab]

What with the random sounds at 0:48, 3:16?

[niteshgupta]

One doubt.. should not we have l = start to find the end index to reduce the initial sub array size?

[Heartless-hekm]

your algorithm will fail if first appearance of pivot is the very first element.
first have solid algo then make clip, i was not expecting this from you.

[akhilsharma]

Why did you take mid=l+(r-l)/2 and not mid=(l+r)/2. Why does the second one give error in some cases. Can you please answer this?

[ajithravindran]

Congrats on 1K, have you reached 4K watch hours?

[techchamp]

Damn!!! hot girl, I sit and listen to all DS& Algo now...