Facebook Interview Questions | Leetcode — 34 Medium
Leetcode Question 34 — This is the most in-detail explanation you have ever seen. We will solve and understand an [medium] array type of question from Leetcode, question number 34 that already comes in the Facebook interview.
The Questions we have
Given an array of integers nums sorted in non-decreasing order, find the starting and ending position of a given target value.
If the target is not found in the array, return [-1, -1].
You must write an algorithm with O(log n) runtime complexity.
Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]Let’s understand the questions in detail, we have an array that is sorted and in ascending order. We have a target value, where we have to find the first index number and last index number that the target value found in the array if we don’t find then return [-1,-1]. In the example, we can see, nums are the array and target = 8, so the first index is [3] from left to right, and the end index is [4].
Strategy:
In a brute-force mindset, we can use two loops from left to right and right to left to find the first and last value, but that will be not an efficient solution, and the question mentions using O(log n) time complexity.
You must write an algorithm with O(log n) runtime complexity.
As we can see, the array is sorted and ordered in ascending order so we can use Binary search. But, how we will use it to find two values by not writing them twice.
So let’s visualize the process:
Here, we will check that is the middle of the program is equal to our target number, if yes then, check left and right for the first starting number that matches with the target and again checks for the last end number.
From the picture index [2] is our middle that matches with our targeted number, but will are not sure that is it the first one that started in the array. So will divide the array and check the left part(green) to check for the first target. This green part will be our new array.
Again, we will repeat this process and find our first targeted value.
Then will again start from the first to find our last target value that site in the last. As we find our first one from the left, now we will check from the right to get that.
Following the same algorithm, we will find our end value.
Now let's see the code and understand step by step:
Don’t submit this code. This code you can use to understand the algorithm we discuss above. You can run to check the output.
# output of the code
values: -1 0 5
start,end,mid: 0 5 2
else asn: 2
Go Left-> end value: 1
start,end,mid: 0 1 0
start: 1
start,end,mid: 1 1 1
else asn: 1
Go Left-> end value: 0
outer while: 1
retrin firsrt index: 1
values: -1 0 5
start,end,mid: 0 5 2
else asn: 2
Go Right-> Start value: 3
start,end,mid: 3 5 4
end: 3
start,end,mid: 3 3 3
end: 2
outer while: 2
[1, 2]Step by step Explanation:
From Main Function:
nums = [5,7,7,8,8,10]; target = 7; Output = [1,2]Start
End — (Doc View)
If you don’t understand, please use pen and paper and try to practice by yourself.
If you find any problem with the code or the explanation, let me know.
Now, you can see that this is the most widely explained article that maybe you never saw. Hahaa...
I also explain in Bangla Language in my YouTube video. (It’s my first time so ignore pardon me)
If you like my article then Follow me to get more posts on tech. Also, If you have any suggestions please comment and like, and share.
— — — — — — Get my More links Here: bio.link/imash — — — — — — —
