Here we will be providing you the thought process and approaches with Time and Space complexity for each problems from the Array Section of Love Babbar’s SDE Sheet.
6) 910. Smallest Range II
You are given an integer array nums and an integer k. For each index i where 0 <= i < nums.length, change nums[i] to be either nums[i] + k or nums[i] – k.The score of nums is the difference between the maximum and minimum elements in nums. Return the minimum score of nums after changing the values at each index.
Input: nums = [1,3,6], k = 3 Output: 3
Explanation: Change nums to be [4, 6, 3].
The score is max(nums) – min(nums)= 6 – 3 = 3.
Approach:
1) Sort the arr and ans= arr[n-1] – arr[0]
2) The lowest value will be added by k and highest value will be subtracted by k.
3) Now while adding k to lowest the 2nd lowest might become less then the earlier lowest.
4) Similarly while subtracting k from highest the 2nd highest might get > earlier highest.
5) Iterate in the array and check if after adding k to lowest the ith num < lowest
- If yes update minn = min(arr[0]+k,arr[i+1]-k)
- Check for max now, maxx = max(arr[n-1]-k , arr[i]+k) Then find ans = min(ans,maxx-minn)
TC = O(nlogn) Sc = O(1)
7) 287. Find the Duplicate Number
Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive. There is only one repeated number in nums, return this repeated number. You must solve the problem without modifying the array nums and uses only constant extra space.
Input: nums = [1,3,4,2,2] , Output: 2
Input: nums = [2,2,2,2,2] , Output: 2
Approach:
Since the elements will be from [1,n] , therefore our answer lies within that range
Steps:
1) we will use binary search and find the number of elements in the i/p arr that are <= mid
2) Initialize st=1 en = n-1 and run a loop
3) if cnt is <= mid than our answer lies in the 2nd half hence, st = mid+1
4) else en = mid-1
5) return st
TC = O(nlogn) Sc = O(1)
8) Merge Sorted Array
You are given two integer arrays nums1 and nums2, sorted in non-decreasing order, and two integers m and n, representing the number of elements in nums1 and nums2 respectively.Merge nums1 and nums2 into a single array sorted in non-decreasing order. Do not use extra space store the values in nums1.
Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
Output: [1,2,2,3,5,6]
Explanation: The arrays we are merging are [1,2,3] and [2,5,6].
The result of the merge is [1,2,2,3,5,6] with the underlined elements coming from nums1
Approach:
corner cases: 1) m=0 , nums1 = nums2 return;
2) n =0, return
Steps:
1)iterate from the end of nums1.
- Check if m>=0 and the values of nums1[m-1] and nums2[n-1] whichever is greater insert at the ith index and decrement either m or n accordingly.
- Check if n==0 break
9) Merge Intervals
Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.
Input: intervals = [[1,3],[2,6],[8,10],[15,18]] Output:
[[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].
Approach:
- sort the vector according to the start time
- initialize, st = v[0][0] , en = v[0][1]
- iterate over the vector,
- if start of each element is <= en, update en = max(en , v[i][1])
- Else insert {st,en} in our ans vector and update st= v[i][0],
- en = v[i][1]
- 4.after iterarting insert the {st,en} in ans vector , return ans;
10) Next Permutation
A permutation of an array of integers is an arrangement of its members into a sequence or linear order.
For example, for arr = [1,2,3], the following are considered permutations of arr: [1,2,3], [1,3,2], [3,1,2], [2,3,1].
The next permutation of an array of integers is the next lexicographically greater permutation of its integer. More formally, if all the permutations of the array are sorted in one container according to their lexicographical order, then the next permutation of that array is the permutation that follows it in the sorted container. If such arrangement is not possible, the array must be rearranged as the lowest possible order (i.e., sorted in ascending order).
- For example, the next permutation of arr = [1,2,3] is [1,3,2].
- Similarly, the next permutation of arr = [2,3,1] is [3,1,2].
- While the next permutation of arr = [3,2,1] is [1,2,3] because [3,2,1] does not have a lexicographical larger rearrangement.
Given an array of integers nums, find the next permutation of nums.
Eg: input: 1 2 3 4 2 6 7 18 12 9 0
Output 1 2 3 4 2 6 9 0 7 12 18
Approach:
Steps:
1) if arr in decreasing order return reverse of the arr ie. If 3,2,1 return 1,2,3
2) if not, iterate from 2nd last index and check if(arr[i] < arr[i+1]) if yes break; this means we found a no. that can be interchanged to make next permutation. Here i = 6 (arr[i] = 7)
3) Now iterate from the last index till the ith index (i we get from step 2) if(arr[j]>arr[i]) break; here j = 9 (arr[j]=9)
4) swap arr[i] & arr[j] //1 2 3 4 2 6 9 18 12 7 0
5) reverse the arr from i+1 th index to last //1 2 3 4 2 6 9 0 7 12 18
TC = O(n) Sc = O(1)
We will be adding the rest of the notes for other topics soon. Also stay updates for the next 5 problems. We will be trying to upload as soon as possible. Thank You and keep supporting.
