Love Babbar’s SDE Sheet Notes for Array Section With Time and Space Complexity | Problem 1-5

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

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:

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.

Check other Topics