Subarrays - Challenges | Questions asked by Top MNC's |

 Array Challenges 

Maximum Sum Subarray Array  

1. Brute Force:  

Idea: For each subarray arr[i..j], calculate its sum. 

Time Complexity: O(N3 ) 

Space Complexity: O(1) 

 

2. Prefix Sum Technique: 

Idea: For each subarray arr[i..j], calculate its sum. Using prefix sum can 

reduce time to calculate the sum of arr[i..j] to O(1) 

Time Complexity: O(N2 ) 

Space Complexity: O(N) 

  

3. Kadane’s Algorithm: 

Idea: Start taking the sum of the array, as soon as it gets negative, discard the current subarray, and start a new sum. 

Time Complexity: O(N) 

Space Complexity: O(1) 

  


 Maximum Sum Circular Subarray: 

 

Idea: There will 2 cases, 

  


To get the Min subarray we multiply the array by -1 and get the maximum sum subarray. 

Time Complexity: O(N) 

  



Pair Target Sum Problem 

Find whether there exist 2 numbers that sum to K. 

Important: The Array should be sorted for two pointer approach. 

Idea: keep a low and high pointer, decide which pointer to move on the basis of arr[low] + arr[high]. 

Time Complexity: O(N) 

Space Complexity: O(1) 


Comments

Popular posts from this blog

Arrays - Q's asked by Top MNC's

Strings Challenges | C++ Placement