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

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


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]



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]


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]



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

2) reverse the 1st 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


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

Approach 2: Using Kadane’s Algo


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.

Check other Topics

Raj Verma is a passionate technologist with a background in software engineering and content creation. He leverages his experience to empower job seekers, particularly those new to the field, with the latest industry insights and resources to land their dream careers. As the founder of TechAtPhone, Raj is dedicated to fostering a thriving tech community where knowledge is shared and career aspirations are realized.