|
Question |
Answer |
|
start learning
|
|
- Idziemy przez tablice od lewej do prawej - W każdym momencie, znamy wartosc najwiekszej sumy podtablicy konczocej sie w tym indeksie (max_ending_here) - za każdym razem uaktualniamy aktualna najwieksza sume (max_ending_here > max_so_far)
|
|
|
What problem does Kadane algorithm solve start learning
|
|
Given an array arr[] of size N. The task is to find the sum of the contiguous subarray within a arr[] with the largest sum.
|
|
|
Given an array arr[] of size N-1 with integers in the range of [1, N], the task is to find the missing number from the first N integers. start learning
|
|
|
|
|
Trapping Rain Water - explain problem start learning
|
|
Given an array of N non-negative integers arr[] representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.
|
|
|
Trapping Rain Water - naive implementation start learning
|
|
The amount of water that will be stored in this column is min(a,b) – array[i], add this value to the total amount of water stored, (min(left[i], right[i]) – arr[i])
|
|
|
Trapping Rain Water - efficent implementation start learning
|
|
like naive, but precalculate left and right highest. For left go from the beginning to end and for each index save max value. Similarly for right go from the end to the beginning.
|
|
|
Explain Maximum Product Subarray start learning
|
|
Given an array that contains both positive and negative integers, the task is to find the product of the maximum product subarray.
|
|
|
Maximum Product Subarray using Kadane’s Algorithm start learning
|
|
Use 3 variables, max_so_far, max_ending_here & min_ending_here For every index, the maximum number ending at that index will be the maximum(arr[i], max_ending_here * arr[i], min_ending_here[i]*arr[i])
|
|
|
Explain: Equilibrium index of an array start learning
|
|
The equilibrium index of an array is an index such that the sum of elements at lower indexes is equal to the sum of elements at higher indexes.
|
|
|
Algorithm: Equilibrium index of an Array using start learning
|
|
Iterate through the array and keep updating the left sum which is initialized as zero. In the loop, we can get the right sum by subtracting the elements one by one. Thanks to Sambasiva for suggesting this solution and providing code for this.
|
|
|
Explain: Leaders in an array start learning
|
|
Write a program to print all the LEADERS in the array. An element is a leader if it is greater than all the elements to its right side. And the rightmost element is always a leader.
|
|
|
Algorithm: Leaders in an array start learning
|
|
The idea is to scan all the elements from right to left in an array and keep track of the maximum till now. When the maximum changes its value, print it.
|
|
|
Time and space complexity: Leaders in an array start learning
|
|
Time Complexity: O(n) Auxiliary Space: O(1)
|
|
|
Time and space complexity: Maximum Subarray Sum Kadane’s Algorithm start learning
|
|
Time Complexity: O(N) Auxiliary Space: O(1)
|
|
|
Time and space complexity: Find the Missing Number start learning
|
|
Time Complexity: O(N) Auxiliary Space: O(1)
|
|
|
Time and space complexity: Trapping Rain Water start learning
|
|
Time Complexity: O(N). Only one traversal of the array is needed, So time Complexity is O(N). Space Complexity: O(N). Two extra arrays are needed, each of size N.
|
|
|
Time and space complexity: Maximum Product Subarray start learning
|
|
Time Complexity: O(N) Auxiliary Space: O(1)
|
|
|
Time and space complexity: Equilibrium index of an array start learning
|
|
Time Complexity: O(N) Auxiliary Space: O(1)
|
|
|
