Array Typical Programs
Concepts of DP:-
[1] https://www.geeksforgeeks.org/dynamic-programming/
https://www.geeksforgeeks.org/maximum-product-subarray/
[1] https://www.geeksforgeeks.org/printing-maximum-sum-increasing-subsequence/
[2] https://www.geeksforgeeks.org/count-number-of-ways-to-cover-a-distance/
[3] https://www.geeksforgeeks.org/coin-change-dp-7/
[4] https://www.geeksforgeeks.org/0-1-knapsack-problem-dp-10/
[5] https://www.geeksforgeeks.org/cutting-a-rod-dp-13/
[6] https://www.geeksforgeeks.org/two-water-jug-puzzle/
[7] https://www.geeksforgeeks.org/count-ways-reach-nth-stair/
[8] https://www.geeksforgeeks.org/longest-palindromic-subsequence-dp-12/
[9] https://www.geeksforgeeks.org/count-possible-paths-top-left-bottom-right-nxm-matrix/
[10] https://www.geeksforgeeks.org/count-strings-can-formed-using-b-c-given-constraints/
[11] https://www.geeksforgeeks.org/count-the-number-of-ways-to-traverse-a-matrix/
[12] https://www.geeksforgeeks.org/matrix-chain-multiplication-a-on2-solution/
--------------------------------------------------------------------------------------------------------------------------
Find length of the largest region in Boolean Matrix
Consider a matrix with rows and columns, where each cell contains either a ‘0’ or a ‘1’ and any cell containing a 1 is called a filled cell. Two cells are said to be connected if they are adjacent to each other horizontally, vertically, or diagonally .If one or more filled cells are also connected, they form a region. find the length of the largest region.
Examples:
Input : M[][5] = { 0 0 1 1 0
1 0 1 1 0
0 1 0 0 0
0 0 0 0 1 }
Output : 6
Ex: in the following example, there are 2 regions one with length 1 and the other as 6.
so largest region : 6
Idea is based on the problem or finding number of islands in Boolean 2D-matrix
A cell in 2D matrix can be connected to at most 8 neighbors. So in DFS, we make recursive calls for 8 neighbors. We keep track of the visited 1’s in every DFS and update maximum length region.
Below is implementation of above idea.
// Program to find the length of the largest
// region in boolean 2D-matrix
#include<bits/stdc++.h>
using namespace std;
#define ROW 4
#define COL 5
// A function to check if a given cell (row, col)
// can be included in DFS
int isSafe(int M[][COL], int row, int col,
bool visited[][COL])
{
// row number is in range, column number is in
// range and value is 1 and not yet visited
return (row >= 0) && (row < ROW) &&
(col >= 0) && (col < COL) &&
(M[row][col] && !visited[row][col]);
}
// A utility function to do DFS for a 2D boolean
// matrix. It only considers the 8 neighbours as
// adjacent vertices
void DFS(int M[][COL], int row, int col,
bool visited[][COL], int &count)
{
// These arrays are used to get row and column
// numbers of 8 neighbours of a given cell
static int rowNbr[] = {-1, -1, -1, 0, 0, 1, 1, 1};
static int colNbr[] = {-1, 0, 1, -1, 1, -1, 0, 1};
// Mark this cell as visited
visited[row][col] = true;
// Recur for all connected neighbours
for (int k = 0; k < 8; ++k)
{
if (isSafe(M, row + rowNbr[k], col + colNbr[k],
visited))
{
// increment region length by one
count++;
DFS(M, row + rowNbr[k], col + colNbr[k],
visited, count);
}
}
}
// The main function that returns largest length region
// of a given boolean 2D matrix
int largestRegion(int M[][COL])
{
// Make a bool array to mark visited cells.
// Initially all cells are unvisited
bool visited[ROW][COL];
memset(visited, 0, sizeof(visited));
// Initialize result as 0 and travesle through the
// all cells of given matrix
int result = INT_MIN;
for (int i = 0; i < ROW; ++i)
{
for (int j = 0; j < COL; ++j)
{
// If a cell with value 1 is not
if (M[i][j] && !visited[i][j])
{
// visited yet, then new region found
int count = 1 ;
DFS(M, i, j, visited , count);
// maximum region
result = max(result , count);
}
}
}
return result ;
}
// Driver program to test above function
int main()
{
int M[][COL] = { {0, 0, 1, 1, 0},
{1, 0, 1, 1, 0},
{0, 1, 0, 0, 0},
{0, 0, 0, 0, 1}};
cout << largestRegion(M);
return 0;
}
Output:
6
Time complexity: O(ROW x COL)
--------------------------------------------------------------------------------------------------------------------------
Leaders in an array
Write a program to print all the LEADERS in the array. An element is leader if it is greater than all the elements to its right side. And the rightmost element is always a leader. For example int the array {16, 17, 4, 3, 5, 2}, leaders are 17, 5 and 2.
Let the input array be arr[] and size of the array be size.
#include<iostream>
using namespace std;
/*C++ Function to print leaders in an array */
void printLeaders(int arr[], int size)
{
for (int i = 0; i < size; i++)
{
int j;
for (j = i+1; j < size; j++)
{
if (arr[i] <= arr[j])
break;
}
if (j == size) // the loop didn't break
cout << arr[i] << " ";
}
}
/* Driver program to test above function */
int main()
{
int arr[] = {16, 17, 4, 3, 5, 2};
int n = sizeof(arr)/sizeof(arr[0]);
printLeaders(arr, n);
return 0;
}
Output:
17 5 2
Time Complexity: O(n*n)
Method 2 (Scan from right)
Scan all the elements from right to left in array and keep track of maximum till now. When maximum changes it’s value, print it.
#include <iostream>
using namespace std;
/* C++ Function to print leaders in an array */
void printLeaders(int arr[], int size)
{
int max_from_right = arr[size-1];
/* Rightmost element is always leader */
cout << max_from_right << " ";
for (int i = size-2; i >= 0; i--)
{
if (max_from_right < arr[i])
{
max_from_right = arr[i];
cout << max_from_right << " ";
}
}
}
/* Driver program to test above function*/
int main()
{
int arr[] = {16, 17, 4, 3, 5, 2};
int n = sizeof(arr)/sizeof(arr[0]);
printLeaders(arr, n);
return 0;
}
Output:
2 5 17
Time Complexity: O(n)
class LeadersInArray
{
/* Java Function to print leaders in an array */
void printLeaders(int arr[], int size)
{
int max_from_right = arr[size-1];
/* Rightmost element is always leader */
System.out.print(max_from_right + " ");
for (int i = size-2; i >= 0; i--)
{
if (max_from_right < arr[i])
{
max_from_right = arr[i];
System.out.print(max_from_right + " ");
}
}
}
/* Driver program to test above functions */
public static void main(String[] args)
{
LeadersInArray lead = new LeadersInArray();
int arr[] = new int[]{16, 17, 4, 3, 5, 2};
int n = arr.length;
lead.printLeaders(arr, n);
}
}
-------------------------------------------------------------------------------------------------------------------------------------------------------
Find the Number Occurring Odd Number of Times
Given an array of positive integers. All numbers occur even number of times except one number which occurs odd number of times. Find the number in O(n) time & constant space.
Examples :
Input : arr = {1, 2, 3, 2, 3, 1, 3}
Output : 3
Input : arr = {5, 7, 2, 7, 5, 2, 5}
Output : 5
A Better Solution is to use Hashing. Use array elements as key and their counts as value. Create an empty hash table. One by one traverse the given array elements and store counts. Time complexity of this solution is O(n). But it requires extra space for hashing.
Program :
// C++ program to find the element
// occurring odd number of times
#include <bits/stdc++.h>
using namespace std;
// function to find the element
// occurring odd number of times
int getOddOccurrence(int arr[],int size)
{
// Defining HashMap in C++
unordered_map<int, int> hash;
// Putting all elements into the HashMap
for(int i = 0; i < size; i++)
{
hash[arr[i]]++;
}
// Iterate through HashMap to check an element
// occurring odd number of times and return it
for(auto i : hash)
{
if(i.second % 2 != 0)
{
return i.first;
}
}
return -1;
}
// Driver code
int main()
{
int arr[] = { 2, 3, 5, 4, 5, 2, 4,
3, 5, 2, 4, 4, 2 };
int n = sizeof(arr) / sizeof(arr[0]);
// Function calling
cout << getOddOccurrence(arr, n);
return 0;
}
// This code is contributed by codeMan_d.
Output :
5
// Java program to find the element occurring odd
// number of times
import java.io.*;
import java.util.HashMap;
class OddOccurrence
{
// function to find the element occurring odd
// number of times
static int getOddOccurrence(int arr[], int n)
{
HashMap<Integer,Integer> hmap = new HashMap<>();
// Putting all elements into the HashMap
for(int i = 0; i < n; i++)
{
if(hmap.containsKey(arr[i]))
{
int val = hmap.get(arr[i]);
// If array element is already present then
// increase the count of that element.
hmap.put(arr[i], val + 1);
}
else
// if array element is not present then put
// element into the HashMap and initialize
// the count to one.
hmap.put(arr[i], 1);
}
// Checking for odd occurrence of each element present
// in the HashMap
for(Integer a:hmap.keySet())
{
if(hmap.get(a) % 2 != 0)
return a;
}
return -1;
}
// driver code
public static void main(String[] args)
{
int arr[] = new int[]{2, 3, 5, 4, 5, 2, 4, 3, 5, 2, 4, 4, 2};
int n = arr.length;
System.out.println(getOddOccurrence(arr, n));
}
}
// This code is contributed by Kamal Rawal
Output :
5
// C++ program to find the element
// occurring odd number of times
#include <bits/stdc++.h>
using namespace std;
// Function to find element occurring
// odd number of times
int getOddOccurrence(int ar[], int ar_size)
{
int res = 0;
for (int i = 0; i < ar_size; i++)
res = res ^ ar[i];
return res;
}
/* Diver function to test above function */
int main()
{
int ar[] = {2, 3, 5, 4, 5, 2, 4, 3, 5, 2, 4, 4, 2};
int n = sizeof(ar)/sizeof(ar[0]);
// Function calling
cout << getOddOccurrence(ar, n);
return 0;
}
Output :
5
//Java program to find the element occurring odd number of times
class OddOccurance
{
int getOddOccurrence(int ar[], int ar_size)
{
int i;
int res = 0;
for (i = 0; i < ar_size; i++)
{
res = res ^ ar[i];
}
return res;
}
public static void main(String[] args)
{
OddOccurance occur = new OddOccurance();
int ar[] = new int[]{2, 3, 5, 4, 5, 2, 4, 3, 5, 2, 4, 4, 2};
int n = ar.length;
System.out.println(occur.getOddOccurrence(ar, n));
}
}
// This code has been contributed by Mayank Jaiswal
Output :
5
Time Complexity: O(n)
-------------------------------------------------------------------------------------------------------------------------------------------------------
Next Greater Element
Given an array, print the Next Greater Element (NGE) for every element. The Next greater Element for an element x is the first greater element on the right side of x in array. Elements for which no greater element exist, consider next greater element as -1.
Examples:
a) For any array, rightmost element always has next greater element as -1.
b) For an array which is sorted in decreasing order, all elements have next greater element as -1.
c) For the input array [4, 5, 2, 25}, the next greater elements for each element are as follows.
Element NGE
4 --> 5
5 --> 25
2 --> 25
25 --> -1
// A Stack based C++ program to find next
// greater element for all array elements.
#include <bits/stdc++.h>
using namespace std;
/* prints element and NGE pair for all
elements of arr[] of size n */
void printNGE(int arr[], int n) {
stack < int > s;
/* push the first element to stack */
s.push(arr[0]);
// iterate for rest of the elements
for (int i = 1; i < n; i++) {
if (s.empty()) {
s.push(arr[i]);
continue;
}
/* if stack is not empty, then
pop an element from stack.
If the popped element is smaller
than next, then
a) print the pair
b) keep popping while elements are
smaller and stack is not empty */
while (s.empty() == false && s.top() < arr[i])
{
cout << s.top() << " --> " << arr[i] << endl;
s.pop();
}
/* push next to stack so that we can find
next greater for it */
s.push(arr[i]);
}
/* After iterating over the loop, the remaining
elements in stack do not have the next greater
element, so print -1 for them */
while (s.empty() == false) {
cout << s.top() << " --> " << -1 << endl;
s.pop();
}
}
/* Driver program to test above functions */
int main() {
int arr[] = {11, 13, 21, 3};
int n = sizeof(arr) / sizeof(arr[0]);
printNGE(arr, n);
return 0;
}
Output:
11 -- 13
13 -- 21
3 -- -1
21 -- -1
Time Complexity: O(n^2). The worst case occurs when all elements are sorted in decreasing order. If elements are sorted in decreasing order, then every element is processed at most 4 times.
a) Initially pushed to the stack.
b) Popped from the stack when next element is being processed.
c) Pushed back to the stack because next element is smaller.
d) Popped from the stack in step 3 of algo.
-------------------------------------------------------------------------------------------------------------------------------------------
Find the longest length Palindromic substring in the given string.
---------------------------------------------------------------------------------------------------------------------------------------------
#include <bits/stdc++.h>
using namespace std;
#define NO_OF_CHARS 256
/* function to check whether two strings are anagram of each other */
bool areAnagram(string str1, string str2)
{
// Create two count arrays and initialize all values as 0
int count[NO_OF_CHARS] = {0};
int i;
// For each character in input strings, increment count in
// the corresponding count array
for (i = 0; str1[i] && str2[i]; i++)
{
count[str1[i]]++;
count[str2[i]]--;
}
// If both strings are of different length. Removing this condition
// will make the program fail for strings like "aaca" and "aca"
if (str1[i] || str2[i])
return false;
// See if there is any non-zero value in count array
for (i = 0; i < NO_OF_CHARS; i++)
if (count[i])
return false;
return true;
}
// Java program to Print all pairs of
// anagrams in a given array of strings
public class GFG
{
static final int NO_OF_CHARS = 256;
/* function to check whether two
strings are anagram of each other */
static boolean areAnagram(String str1, String str2)
{
// Create two count arrays and initialize
// all values as 0
int[] count = new int[NO_OF_CHARS];
int i;
// For each character in input strings,
// increment count in the corresponding
// count array
for (i = 0; i < str1.length() && i < str2.length();
i++)
{
count[str1.charAt(i)]++;
count[str2.charAt(i)]--;
}
// If both strings are of different length.
// Removing this condition will make the program
// fail for strings like "aaca" and "aca"
if (str1.length() != str2.length())
return false;
// See if there is any non-zero value in
// count array
for (i = 0; i < NO_OF_CHARS; i++)
if (count[i] != 0)
return false;
return true;
}
// This function prints all anagram pairs in a
// given array of strigns
static void findAllAnagrams(String arr[], int n)
{
for (int i = 0; i < n; i++)
for (int j = i+1; j < n; j++)
if (areAnagram(arr[i], arr[j]))
System.out.println(arr[i] +
" is anagram of " + arr[j]);
}
/* Driver program to test to pront printDups*/
public static void main(String args[])
{
String arr[] = {"geeksquiz", "geeksforgeeks",
"abcd", "forgeeksgeeks",
"zuiqkeegs"};
int n = arr.length;
findAllAnagrams(arr, n);
}
}
// This code is contributed by Sumit Ghosh
Output:
geeksquiz is anagram of zuiqkeegs
geeksforgeeks is anagram of forgeeksgeeks
The time complexity of the above solution is O(n2*m) where n is number of strings and m is maximum length of a string.
-------------------------------------------------------------------------------------------------------------------------------------------------------
Find the Clone of a linked list with random or arbitrary pointer.
-------------------------------------------------------------------------------------------------------------------------------------------------------
Given a Linked List of characters, find weather it is palindrome or not.
-------------------------------------------------------------------------------------------------------------------------------------------------------
Given a binary string, count number of substrings that start and end with 1.
Given a binary string, count number of substrings that start and end with 1. For example, if the input string is “00100101”, then there are three substrings “1001”, “100101” and “101”.
We can find count in O(n) using a single traversal of input string. Following are steps.
a) Count the number of 1’s. Let the count of 1’s be m.
b) Return m(m-1)/2
The idea is to count total number of possible pairs of 1’s.
// A O(n) C++ program to count number of
// substrings starting and ending with 1
#include<iostream>
using namespace std;
int countSubStr(char str[])
{
int m = 0; // Count of 1's in input string
// Traverse input string and count of 1's in it
for (int i=0; str[i] !='\0'; i++)
{
if (str[i] == '1')
m++;
}
// Return count of possible pairs among m 1's
return m*(m-1)/2;
}
// Driver program to test above function
int main()
{
char str[] = "00100101";
cout << countSubStr(str);
return 0;
}
Output:
3
------------------------------------------------------------------------------------------------------------------------------------------------------
/*
Given a sorted array and a number x, find the pair in array whose sum is closest to x
Given a sorted array and a number x, find a pair in array whose sum is closest to x.
Examples:
Input: arr[] = {10, 22, 28, 29, 30, 40}, x = 54
Output: 22 and 30
Input: arr[] = {1, 3, 4, 7, 10}, x = 15
Output: 4 and 10
*/
void closestPair(int arr[], int size, int sum)
{
int j = size - 1;
int m = 0;
int l = 0;
int i =0;
while(i<j)
{
if (arr[i] + arr[j] <= sum)
{
m = i;
l = j;
i++;
j--;
}
else if (arr[i] + arr[j] > sum)
{
j--;
}
else
{
i++;
}
}
cout<<"("<<m<<","<<l<<")";
}
------------------------------------------------------------------------------------------------------------------------------------------------------
/*
Remove duplicates from a string in O(1) extra space
Given a string str of lowercase characters, the task is to remove duplicates and return a resultant string without modifying
the order of characters in the original string.
Examples:
Input: str = "geeksforgeeks"
Output: geksfor
Input: str = "characters"
Output: chartes
*/
string removeDuplicates(string str)
{
int counter = 0;
int x = 1;
int j = 0;
int len = 0;
for(int i =0;i<str.length();i++)
{
x = str[i] - 97;
if (0 == (counter&(1<<x)))
{
counter = counter | (1<<x);
str[len] = x + 'a';
len++;
}
}
string str1 = str.substr(0, len);
return str1;
}
--------------------------------------------------------------------------------------------------------------------------------------------
Longest subarray having maximum sum
Given an array arr[] containing n integers. The problem is to find the length of the subarray having maximum sum. If there exists two or more subarrays with maximum sum then print the length of the longest subarray.
Examples:
Input : arr[] = {5, -2, -1, 3, -4}
Output : 4
There are two subarrays with maximum sum:
First is {5}
Second is {5, -2, -1, 3}
Therefore longest one is of length 4.
Input : arr[] = {-2, -3, 4, -1, -2, 1, 5, -3}
Output : 5
The subarray is {4, -1, -2, 1, 5}
An efficient solution is to optimize the brute force technique of finding the subarray in above approach using the concept of sliding window technique. We can maintain a preCount array to find number of 1’s present in a subarray in O(1) time complexity.
Below is the implementation of above idea:
Approach: Following are the steps:
Find the maximum sum contiguous subarray. Let this sum be maxSum.
Find the length of the longest subarray having sum equal to maxSum. Refer this post.
// C++ implementation to find the length of the longest
// subarray having maximum sum
#include <bits/stdc++.h>
using namespace std;
// function to find the maximum sum that
// exists in a subarray
int maxSubArraySum(int arr[], int size)
{
int max_so_far = arr[0];
int curr_max = arr[0];
for (int i = 1; i < size; i++) {
curr_max = max(arr[i], curr_max + arr[i]);
max_so_far = max(max_so_far, curr_max);
}
return max_so_far;
}
// function to find the length of longest
// subarray having sum k
int lenOfLongSubarrWithGivenSum(int arr[], int n, int k)
{
// unordered_map 'um' implemented
// as hash table
unordered_map<int, int> um;
int sum = 0, maxLen = 0;
// traverse the given array
for (int i = 0; i < n; i++) {
// accumulate sum
sum += arr[i];
// when subarray starts from index '0'
if (sum == k)
maxLen = i + 1;
// make an entry for 'sum' if it is
// not present in 'um'
if (um.find(sum) == um.end())
um[sum] = i;
// check if 'sum-k' is present in 'um'
// or not
if (um.find(sum - k) != um.end()) {
// update maxLength
if (maxLen < (i - um[sum - k]))
maxLen = i - um[sum - k];
}
}
// required maximum length
return maxLen;
}
// function to find the length of the longest
// subarray having maximum sum
int lenLongSubarrWithMaxSum(int arr[], int n)
{
int maxSum = maxSubArraySum(arr, n);
return lenOfLongSubarrWithGivenSum(arr, n, maxSum);
}
// Driver program to test above
int main()
{
int arr[] = { 5, -2, -1, 3, -4 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Length of longest subarray having maximum sum = "
<< lenLongSubarrWithMaxSum(arr, n);
return 0;
}
Output:
Length of longest subarray having maximum sum = 4
Time Complexity: O(n).
Auxiliary Space: O(n).
--------------------------------------------------------------------------------------------------------------------------------------------
Function to check if a singly linked list is palindrome
Given a singly linked list of characters, write a function that returns true if the given list is palindrome, else false.
METHOD 1 (Use a Stack)
A simple solution is to use a stack of list nodes. This mainly involves three steps.
1) Traverse the given list from head to tail and push every visited node to stack.
2) Traverse the list again. For every visited node, pop a node from stack and compare data of popped node with currently visited node.
3) If all nodes matched, then return true, else false.
Time complexity of above method is O(n), but it requires O(n) extra space. Following methods solve this with constant extra space.
#include<iostream>
#include<stack>
using namespace std;
class Node {
public:
int data;
Node(int d){
data = d;
}
Node *ptr;
};
int isPalin(Node* head){
Node* slow= head;
stack <int> s;
int i;
int isPalindrome = 1; // 0 = false & 1 = true
while(slow != NULL){
s.push(slow->data);
slow = slow->ptr;
}
while(head != NULL ){
i=s.top();
s.pop();
if(head -> data == i){false
isPalindrome = 1;
}else{
isPalindrome = 0;break;
}
head=head->ptr;
}
return isPalindrome;
}
int main(){
Node one = Node(1);
Node two = Node(2);
Node three = Node(3);
Node four = Node(2);
Node five = Node(1);
five.ptr = NULL;
one.ptr = &two;
two.ptr = &three;
three.ptr = &four;
four.ptr = &five;
Node* temp = &one;
int result = isPalin(&one);
if(result == 1)
cout<<"\nisPalindrome is true\n";
else
cout<<"isPalindrome is true\n";
return 0;
}
Output
isPalindrome: true
--------------------------------------------------------------------------------------------------------------------------------------------
Maximum Product Subarray
Given an array that contains both positive and negative integers, find the product of the maximum product subarray. Expected Time complexity is O(n) and only O(1) extra space can be used.
Examples:
Input: arr[] = {6, -3, -10, 0, 2}
Output: 180 // The subarray is {6, -3, -10}
Input: arr[] = {-1, -3, -10, 0, 60}
Output: 60 // The subarray is {60}
Input: arr[] = {-2, -3, 0, -2, -40}
Output: 80 // The subarray is {-2, -40}
The following solution assumes that the given input array always has a positive output. The solution works for all cases mentioned above. It doesn’t work for arrays like {0, 0, -20, 0}, {0, 0, 0}.. etc. The solution can be easily modified to handle this case.
It is similar to Largest Sum Contiguous Subarray problem. The only thing to note here is, maximum product can also be obtained by minimum (negative) product ending with the previous element multiplied by this element. For example, in array {12, 2, -3, -5, -6, -2}, when we are at element -2, the maximum product is multiplication of, minimum product ending with -6 and -2.
Longest subarray having maximum sum
Given an array arr[] containing n integers. The problem is to find the length of the subarray having maximum sum. If there exists two or more subarrays with maximum sum then print the length of the longest subarray.
Examples:
Input : arr[] = {5, -2, -1, 3, -4}
Output : 4
There are two subarrays with maximum sum:
First is {5}
Second is {5, -2, -1, 3}
Therefore longest one is of length 4.
Input : arr[] = {-2, -3, 4, -1, -2, 1, 5, -3}
Output : 5
The subarray is {4, -1, -2, 1, 5}
An efficient solution is to optimize the brute force technique of finding the subarray in above approach using the concept of sliding window technique. We can maintain a preCount array to find number of 1’s present in a subarray in O(1) time complexity.
Below is the implementation of above idea:
Approach: Following are the steps:
- Find the maximum sum contiguous subarray. Let this sum be maxSum.
- Find the length of the longest subarray having sum equal to maxSum. Refer this post.
// C++ implementation to find the length of the longest
// subarray having maximum sum
#include <bits/stdc++.h>
using namespace std;
// function to find the maximum sum that
// exists in a subarray
int maxSubArraySum(int arr[], int size)
{
int max_so_far = arr[0];
int curr_max = arr[0];
for (int i = 1; i < size; i++) {
curr_max = max(arr[i], curr_max + arr[i]);
max_so_far = max(max_so_far, curr_max);
}
return max_so_far;
}
// function to find the length of longest
// subarray having sum k
int lenOfLongSubarrWithGivenSum(int arr[], int n, int k)
{
// unordered_map 'um' implemented
// as hash table
unordered_map<int, int> um;
int sum = 0, maxLen = 0;
// traverse the given array
for (int i = 0; i < n; i++) {
// accumulate sum
sum += arr[i];
// when subarray starts from index '0'
if (sum == k)
maxLen = i + 1;
// make an entry for 'sum' if it is
// not present in 'um'
if (um.find(sum) == um.end())
um[sum] = i;
// check if 'sum-k' is present in 'um'
// or not
if (um.find(sum - k) != um.end()) {
// update maxLength
if (maxLen < (i - um[sum - k]))
maxLen = i - um[sum - k];
}
}
// required maximum length
return maxLen;
}
// function to find the length of the longest
// subarray having maximum sum
int lenLongSubarrWithMaxSum(int arr[], int n)
{
int maxSum = maxSubArraySum(arr, n);
return lenOfLongSubarrWithGivenSum(arr, n, maxSum);
}
// Driver program to test above
int main()
{
int arr[] = { 5, -2, -1, 3, -4 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Length of longest subarray having maximum sum = "
<< lenLongSubarrWithMaxSum(arr, n);
return 0;
}
Output:
Length of longest subarray having maximum sum = 4
Time Complexity: O(n).
Auxiliary Space: O(n).
// subarray having maximum sum
#include <bits/stdc++.h>
using namespace std;
// function to find the maximum sum that
// exists in a subarray
int maxSubArraySum(int arr[], int size)
{
int max_so_far = arr[0];
int curr_max = arr[0];
for (int i = 1; i < size; i++) {
curr_max = max(arr[i], curr_max + arr[i]);
max_so_far = max(max_so_far, curr_max);
}
return max_so_far;
}
// function to find the length of longest
// subarray having sum k
int lenOfLongSubarrWithGivenSum(int arr[], int n, int k)
{
// unordered_map 'um' implemented
// as hash table
unordered_map<int, int> um;
int sum = 0, maxLen = 0;
// traverse the given array
for (int i = 0; i < n; i++) {
// accumulate sum
sum += arr[i];
// when subarray starts from index '0'
if (sum == k)
maxLen = i + 1;
// make an entry for 'sum' if it is
// not present in 'um'
if (um.find(sum) == um.end())
um[sum] = i;
// check if 'sum-k' is present in 'um'
// or not
if (um.find(sum - k) != um.end()) {
// update maxLength
if (maxLen < (i - um[sum - k]))
maxLen = i - um[sum - k];
}
}
// required maximum length
return maxLen;
}
// function to find the length of the longest
// subarray having maximum sum
int lenLongSubarrWithMaxSum(int arr[], int n)
{
int maxSum = maxSubArraySum(arr, n);
return lenOfLongSubarrWithGivenSum(arr, n, maxSum);
}
// Driver program to test above
int main()
{
int arr[] = { 5, -2, -1, 3, -4 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Length of longest subarray having maximum sum = "
<< lenLongSubarrWithMaxSum(arr, n);
return 0;
}
Output:
Length of longest subarray having maximum sum = 4
Time Complexity: O(n).
Auxiliary Space: O(n).
Maximum Product Subarray
Given an array that contains both positive and negative integers, find the product of the maximum product subarray. Expected Time complexity is O(n) and only O(1) extra space can be used.
Examples:
Input: arr[] = {6, -3, -10, 0, 2}
Output: 180 // The subarray is {6, -3, -10}
Input: arr[] = {-1, -3, -10, 0, 60}
Output: 60 // The subarray is {60}
Input: arr[] = {-2, -3, 0, -2, -40}
Output: 80 // The subarray is {-2, -40}
Output:
Maximum Sub array product is 112
Time Complexity: O(n)
Auxiliary Space: O(1)
Auxiliary Space: O(1)
Find duplicates in O(n) time and O(1) extra space | Set 1
Given an array of n elements which contains elements from 0 to n-1, with any of these numbers appearing any number of times. Find these repeating numbers in O(n) and using only constant memory space.
For example, let n be 7 and array be {1, 2, 3, 1, 3, 6, 6}, the answer should be 1, 3 and 6.
Comments
Post a Comment