LeetCode Questions — Day 2(Binary Search)

Hi coders,
Let get the more complex question in the series of learning Competitive programming.

Problem:1 Search Insert Position
Given a sorted array of distinct integers and a target value, return the index if the target is found.
If not, return the index where it would be if it were inserted in order.
You must write an algorithm with O(log n) runtime complexity.

Solution 1: This took 30–40 min to think for only one case (return the index where it would be if it were inserted in order)

Explanation: In this approach again, I used the binary search since from the last day one thing that is present in my mind is the implementation of it. Hope the code was more understanding to you all, but still I will explain to make it more easy for you all.

Here it started with my condition saying my start should be less than or equal to my end(len(num)-1). I am finding the mid index and the special case for which it took 30 min extra for me today. which is for the case when we have one element in the list and target is also present in that one element, for which I compared the start and len(num)-1 and if its equal. Afterwards I compared that num[end] < target then return end+1 else end which worked for me to solve this one case.

After that my binary search proceed where I looked for my mid element with the target, if it matches return the mid index else if the mid element is less than the target then assign the start as (mid +1) and reiterate, else if the mid element is greater than the target then assign the end as mid-1 and continue the loop.

Solution 2: Having less memory space.

Solution 3: Having less runtime space.

Problem-2: Squares of a Sorted Array
Given an integer array nums sorted in non-decreasing order, return an array of the squares of each number sorted
in non-decreasing order.

Example-1
Input: nums = [-4,-1,0,3,10]
Output: [0,1,9,16,100]
Explanation: After squaring, the array becomes [16,1,0,9,100].
After sorting, it becomes [0,1,9,16,100].

Example-2
Input: nums = [-7,-3,2,3,11]
Output: [4,9,9,49,121]

Constraints:
1 <= nums.length <= 104
-104 <= nums[i] <= 104
nums is sorted in non-decreasing order.

Solution: Guess coders!! this time my code was the efficient one, you all can do it trust me!! #be_consistent

Explanation: In this approach I have used list comprehension to square the numbers of my list and then using the in-built python sort function i had sort the values of the list. Hope it was easy for you all.

Solution 2:(Its just an alternate way but not efficient)

From today’s problem I learned one thing that if you are consistent in your life you can solve any problems in your life, whether its a life based problem or a coding problem one thing remains constant in both of them, your efforts to make it resolved #makeitdone #neverloosingattitude.

Keep Reading, Keep Coding