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.**

### 1) Kth Largest Element in an Array

Given an integer array nums and an integer k, return *the *kth *largest element in the array*. Note that it is the kth largest element in the sorted order, not the kth distinct element.

**Example 1: ****Input: **nums = [3,2,1,5,6,4], k = 2 **Output: **5

**Example 2: ****Input: **nums = [3,2,3,1,2,4,5,5,6], k = 4 **Output: **4

**Approach 1: **

Sort the array and return arr[n-k] **TC = O(nlogn) SC = O(1)**

**Approach 2: **

1) use a min priority queue (min heap)

2)iterate over the array and insert in queue, after inserting check if the size of the queue is greater than k if yes pop the top element

3) return q.top()

**TC = O(nlogk) SC = O(k)**

### 2) Sort 0’s 1’s and 2’s

Given an array of size N containing only 0s, 1s, and 2s; sort the array in ascending order without using sort function.

**Input: **nums = [2,0,2,1,1,0] **Output: **[0,0,1,1,2,2]

**Approach:**** **Using DNF sort

**Steps: **

1) take 3 pointers lo = 0, mid = 0 , hi = n-1

2) run a loop while mid<=hi

- If we find 0 in middle: swap arr[lo] and arr[mid] mid++,lo++
- If we find 1: mid++
- If we find 2: swap mid and hi hi–

**TC = O(n) Sc = O(1)**

### 3) **Move all negative numbers to the beginning & positive numbers to the end**

**Input: **nums = [12,-70,-2,1,-1,0] **Output: **[-70,-2,-1,12,1,0]

#### Approach:

**Steps: **

1) take 2 pointers i = 0, st = 0

2) run a loop while i<n

- If arr[i] == –ve number: swap arr[i] and arr[st] , st++

**TC = O(n) Sc = O(1)**

### 4) **Rotate Array**

Given an array, rotate the array to the right by k steps, where k is non-negative.

**Input: **nums = [1,2,3,4,5,6,7], k = 3 **Output: **[5,6,7,1,2,3,4]

**Explanation:**

rotate 1 steps to the right: [7,1,2,3,4,5,6] rotate 2 steps to the right: [6,7,1,2,3,4,5] rotate 3 steps to the right: [5,6,7,1,2,3,4]

**Approach: **

**Steps**:

1) reverse the array // [ 7,6,5,4,3,2,1 ]

2) reverse the 1^{st} k elements // [ 5,6,7,4,3,2,1 ]

3) reverse the rest elements after k // [5,6,7,1,2,3,4]

**TC = O(n) Sc = O(1)**

### 5) **Maximum Subarray**** (Kadane’s Algo)**

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return *its sum*.

**I/p: **nums = [-2,1,-3,4,-1,2,1,-5,4]

**O/p: **6

**Expln: **[4,-1,2,1] has the largest sum = 6

**Approach1: **

Use 2 for loops and find the largest subarray sum **TC = O(n^2) Sc = O(1)**

**Approach 2: **Using Kadane’s Algo

**Steps: **

1) Use two variables max_ans = 0 and curr_max = 0 curr_max gives us the subarray sum till a particular index.

2) Run a loop from i=0 to the end of array:

- curr_max += arr[i]

- max_ans = maximum between (max_ans and curr_max)

- if curr_max < 0 : update curr_max = 0

**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.