Algorithms

Omów Kadane’s Algorithm

- 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

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.

(1+n)*n/2 - sum(arr)

Trapping Rain Water - explain problem

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

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

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

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

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

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

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

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

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

Time Complexity: O(n) Auxiliary Space: O(1)

Time and space complexity: Maximum Subarray Sum Kadane’s Algorithm

Time Complexity: O(N) Auxiliary Space: O(1)

Time and space complexity: Find the Missing Number

Time Complexity: O(N) Auxiliary Space: O(1)

Time and space complexity: Trapping Rain Water

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

Time Complexity: O(N) Auxiliary Space: O(1)

Time and space complexity: Equilibrium index of an array

Time Complexity: O(N) Auxiliary Space: O(1)