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 2^{nd} 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 2^{nd} 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 2^{nd} 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.