Given an array of N positive integers. The task is to perform the following operations according to the type of query given.
1. Print the maximum pair product in a given range. [L-R]
2. Update Ai with some given value.
Examples:
Input: A={1, 3, 4, 2, 5}
Queries:
Type 1: L = 0, R = 2.
Type 2: i = 1, val = 6
Type 1: L = 0, R = 2.
Output:
12
24
For the query1, the maximum product in a range [0, 2] is 3*4 = 12.
For the query2, after an update, the array becomes [1, 6, 4, 2, 5]
For the query3, the maximum product in a range [0, 2] is 6*4 = 24.
Naive Solution: The brute force approach is to traverse from L to R and check for every pair and then find the maximum product pair among them.
Below is the implementation of the above approach.
C++14
// C++ program to find the maximum// product in a range with updates#include <bits/stdc++.h>using namespace std;// Function to print the maximum product// of any pair in the range [L, R]void query1(vector<int> arr, int n, int L, int R){ int maxProd = 0; // Nested loops to iterate through // all possible pairs in the range for (int i = L; i < R; i++) { for (int j = i + 1; j <= R; j++) { int prod = arr[i] * arr[j]; // Update the maximum product // if a larger product is found if (prod > maxProd) { maxProd = prod; } } } // Print the maximum product // found in the range [L, R] cout << "Maximum product in the range " << L << " and " << R << " is " << maxProd << endl;}// Function to update the value// of arr[i] to valvoid query2(vector<int>& arr, int i, int val){ arr[i] = val;}int main(){ vector<int> arr = { 1, 3, 4, 2, 5 }; int n = arr.size(); // Query 1: Print the maximum product // in the range [L, R] query1(arr, n, 0, 2); // Query 2: Update the value of // arr[i] to val query2(arr, 1, 6); // Query 3: Print the maximum product // in the updated range [L, R] query1(arr, n, 0, 2); return 0;} |
Java
import java.util.Arrays;public class MaxProductRange { // Function to print the maximum product of any pair in the range [L, R] static void query1(int[] arr, int L, int R) { int maxProd = 0; // Nested loops to iterate through all possible pairs in the range for (int i = L; i < R; i++) { for (int j = i + 1; j <= R; j++) { int prod = arr[i] * arr[j]; // Update the maximum product if a larger product is found if (prod > maxProd) { maxProd = prod; } } } System.out.println("Maximum product in the range " + L + " and " + R + " is " + maxProd); } // Function to update the value of arr[i] to val static void query2(int[] arr, int i, int val) { arr[i] = val; } // Driver Code public static void main(String[] args) { int[] arr = {1, 3, 4, 2, 5}; int n = arr.length; query1(arr, 0, 2); query2(arr, 1, 6); query1(arr, 0, 2); }} |
Python3
# Python program to find the maximum# product in a range with updates# Function to print the maximum product# of any pair in the range [L, R]def query1(arr, n, L, R): maxProd = 0 # Nested loops to iterate through # all possible pairs in the range for i in range(L, R): for j in range(i + 1, R + 1): prod = arr[i] * arr[j] # Update the maximum product # if a larger product is found if prod > maxProd: maxProd = prod # Print the maximum product # found in the range [L, R] print(f"Maximum product in the range {L} and {R} is {maxProd}")# Function to update the value# of arr[i] to valdef query2(arr, i, val): arr[i] = valif __name__ == "__main__": arr = [1, 3, 4, 2, 5] n = len(arr) # Query 1: Print the maximum product # in the range [L, R] query1(arr, n, 0, 2) # Query 2: Update the value of # arr[i] to val query2(arr, 1, 6) # Query 3: Print the maximum product # in the updated range [L, R] query1(arr, n, 0, 2) |
C#
using System;using System.Collections.Generic;class GFG{ // Function to print the maximum product // of any pair in the range [L, R] static void Query1(List<int> arr, int L, int R) { int maxProd = 0; // Nested loops to iterate through // all possible pairs in the range for (int i = L; i < R; i++) { for (int j = i + 1; j <= R; j++) { int prod = arr[i] * arr[j]; // Update the maximum product // if a larger product is found if (prod > maxProd) { maxProd = prod; } } } // Print the maximum product // found in the range [L, R] Console.WriteLine($"Maximum product in the range {L} and {R} is {maxProd}"); } // Function to update the value // of arr[i] to val static void Query2(List<int> arr, int i, int val) { arr[i] = val; }//Driver code static void Main(string[] args) { List<int> arr = new List<int> { 1, 3, 4, 2, 5 }; int n = arr.Count; Query1(arr, 0, 2); Query2(arr, 1, 6); Query1(arr, 0, 2); }} |
Javascript
// Function to find the maximum// product in a range with updatesfunction query1(arr, L, R) { let maxProd = 0; // Nested loops to iterate through // all possible pairs in the range for (let i = L; i < R; i++) { for (let j = i + 1; j <= R; j++) { const prod = arr[i] * arr[j]; // Update the maximum product // if a larger product is found if (prod > maxProd) { maxProd = prod; } } } // Print the maximum product // found in the range [L, R] console.log(`Maximum product in the range ${L} and ${R} is ${maxProd}`);}// Function to update the value// of arr[i] to valfunction query2(arr, i, val) { arr[i] = val;}// Driver Codeconst arr = [1, 3, 4, 2, 5];// Query 1: Print the maximum product// in the range [L, R]query1(arr, 0, 2);// Query 2: Update the value of// arr[i] to valquery2(arr, 1, 6);// Query 3: Print the maximum product// in the updated range [L, R]query1(arr, 0, 2); |
Output
Maximum product in the range 0 and 2 is 12 Maximum product in the range 0 and 2 is 24
Time Complexity: O(N^2) for every query to print the maximum product of any pair and O(1) for updation of the value.
Space Complexity: O(1), no extra space is used.
A better solution is to find the first and the second largest number in the range L to R by traversing and then returning their product.
Time Complexity: O(N) for every query.
A efficient solution is to use a segment tree to store the largest and second largest number in the nodes and then return the product of them.
Below is the implementation of above approach.
C++
// C++ program to find the maximum// product in a range with updates#include& lt; bits / stdc++.h & gt;using namespace std;#define ll long long// structure definedstruct segment { // l for largest // sl for second largest ll l; ll sl;};// function to perform queriessegment query(segment* tree, ll index, ll s, ll e, ll qs, ll qe){ segment res; res.l = -1; res.sl = -1; // no overlapping case if (qs & gt; e || qe & lt; s || s & gt; e) { return res; } // complete overlap case if (s& gt; = qs & amp; & e& lt; = qe) { return tree[index]; } // partial overlap case ll mid = (s + e) / 2; // calling left node and right node segment left = query(tree, 2 * index, s, mid, qs, qe); segment right = query(tree, 2 * index + 1, mid + 1, e, qs, qe); // largest of ( left.l, right.l) ll largest = max(left.l, right.l); // compute second largest // second largest will be minimum // of maximum from left and right node ll second_largest = min(max(left.l, right.sl), max(right.l, left.sl)); // store largest and // second_largest in res res.l = largest; res.sl = second_largest; // return the resulting node return res;}// function to update the queryvoid update(segment* tree, ll index, ll s, ll e, ll i, ll val){ // no overlapping case if (i & lt; s || i & gt; e) { return; } // reached leaf node if (s == e) { tree[index].l = val; tree[index].sl = INT_MIN; return; } // partial overlap ll mid = (s + e) / 2; // left subtree call update(tree, 2 * index, s, mid, i, val); // right subtree call update(tree, 2 * index + 1, mid + 1, e, i, val); // largest of ( left.l, right.l) tree[index].l = max(tree[2 * index].l, tree[2 * index + 1].l); // compute second largest // second largest will be // minimum of maximum from left and right node tree[index].sl = min( max(tree[2 * index].l, tree[2 * index + 1].sl), max(tree[2 * index + 1].l, tree[2 * index].sl));}// Function to build the treevoid buildtree(segment* tree, ll* a, ll index, ll s, ll e){ // tree is build bottom to up if (s & gt; e) { return; } // leaf node if (s == e) { tree[index].l = a[s]; tree[index].sl = INT_MIN; return; } ll mid = (s + e) / 2; // calling the left node buildtree(tree, a, 2 * index, s, mid); // calling the right node buildtree(tree, a, 2 * index + 1, mid + 1, e); // largest of ( left.l, right.l) ll largest = max(tree[2 * index].l, tree[2 * index + 1].l); // compute second largest // second largest will be minimum // of maximum from left and right node ll second_largest = min( max(tree[2 * index].l, tree[2 * index + 1].sl), max(tree[2 * index + 1].l, tree[2 * index].sl)); // storing the largest and // second_largest values in the current node tree[index].l = largest; tree[index].sl = second_largest;}// Driver Codeint main(){ // your code goes here ll n = 5; ll a[5] = { 1, 3, 4, 2, 5 }; // allocating memory for segment tree segment* tree = new segment[4 * n + 1]; // buildtree(tree, a, index, start, end) buildtree(tree, a, 1, 0, n - 1); // query section // storing the resulting node segment res = query(tree, 1, 0, n - 1, 0, 2); cout& lt; < " Maximum product in the range& quot; < < " 0 and 2 before update : " < < (res.l * res.sl); // update section // update(tree, index, start, end, i, v) update(tree, 1, 0, n - 1, 1, 6); res = query(tree, 1, 0, n - 1, 0, 2); cout& lt; < " \nMaximum product in the range& quot; < < " 0 and 2 after update : " < < (res.l * res.sl); return 0;} |
Java
// Java program to find the maximum// product in a range with updatesimport java.util.*;public class Main { // structure defined static class Segment { // l for largest // sl for second largest long l; long sl; } // function to perform queries static Segment query(Segment[] tree, int index, int s, int e, int qs, int qe) { Segment res = new Segment(); res.l = -1; res.sl = -1; // no overlapping case if (qs > e || qe < s || s > e) { return res; } // complete overlap case if (s >= qs && e <= qe) { return tree[index]; } int mid = (s + e) / 2; // calling left node and right node Segment left = query(tree, 2 * index, s, mid, qs, qe); Segment right = query(tree, 2 * index + 1, mid + 1, e, qs, qe); // largest of ( left.l, right.l) long largest = Math.max(left.l, right.l); // compute second largest // second largest will be minimum // of maximum from left and right node long second_largest = Math.min(Math.max(left.l, right.sl), Math.max(right.l, left.sl)); // store largest and // second_largest in res res.l = largest; res.sl = second_largest; // return the resulting node return res; } // function to update the query static void update(Segment[] tree, int index, int s, int e, int i, int val) { // no overlapping case if (i < s || i > e) { return; } // reached leaf node if (s == e) { tree[index].l = val; tree[index].sl = Integer.MIN_VALUE; return; } int mid = (s + e) / 2; // partial overlap update(tree, 2 * index, s, mid, i, val); update(tree, 2 * index + 1, mid + 1, e, i, val); tree[index].l = Math.max(tree[2 * index].l, tree[2 * index + 1].l); tree[index].sl = Math.min(Math.max(tree[2 * index].l, tree[2 * index + 1].sl), Math.max(tree[2 * index + 1].l, tree[2 * index].sl)); } // Function to build the tree static void buildtree(Segment[] tree, int[] a, int index, int s, int e) { if (s > e) { return; } if (s == e) { tree[index].l = a[s]; tree[index].sl = Integer.MIN_VALUE; return; } int mid = (s + e) / 2; buildtree(tree, a, 2 * index, s, mid); buildtree(tree, a, 2 * index + 1, mid + 1, e); long largest = Math.max(tree[2 * index].l, tree[2 * index + 1].l); // compute second largest // second largest will be minimum // of maximum from left and right node long second_largest = Math.min(Math.max(tree[2 * index].l, tree[2 * index + 1].sl), Math.max(tree[2 * index + 1].l, tree[2 * index].sl)); // storing the largest and // second_largest values in the current node tree[index].l = largest; tree[index].sl = second_largest; } // Driver code public static void main(String[] args) { int n = 5; int[] a = new int[] { 1, 3, 4, 2, 5 }; // allocating memory for segment tree Segment[] tree = new Segment[4 * n + 1]; // initializing segment tree nodes for (int i = 0; i < 4 * n + 1; i++) { tree[i] = new Segment(); } // building segment tree buildtree(tree, a, 1, 0, n - 1); // query section // storing the resulting node Segment res = query(tree, 1, 0, n - 1, 0, 2); System.out.println("Maximum product in the range " + "0 and 2 before update: " + (res.l * res.sl)); // update section // update(tree, index, start, end, i, v) update(tree, 1, 0, n - 1, 1, 6); res = query(tree, 1, 0, n - 1, 0, 2); System.out.println("\nMaximum product in the range " + "0 and 2 after update: " + (res.l * res.sl)); }} // function to update the query// Function to build the // tree |
Python3
# Python code implementation for the above approach.INT_MAX = 2147483647INT_MIN = -2147483648# structure definedclass segment: # l for largest # sl for second largest def __init__(self, l, sl): self.l = l self.sl = sl # function to perform queriesdef query(tree, index, s, e, qs, qe): res = segment(0, 0) res.l = -1 res.sl = -1 # no overlapping case if qs > e or qe < s or s > e: return res # complete overlap case if s >= qs and e <= qe: return tree[index] # partial overlap case mid = (s + e) // 2 # calling left node and right node left = query(tree, 2 * index, s, mid, qs, qe) right = query(tree, 2 * index + 1, mid + 1, e, qs, qe) # largest of ( left.l, right.l) largest = max(left.l, right.l) # compute second largest # second largest will be minimum # of maximum from left and right node second_largest = min(max(left.l, right.sl), max(right.l, left.sl)) # store largest and # second_largest in res res.l = largest res.sl = second_largest # return the resulting node return res # function to update the querydef update(tree, index, s, e, i, val): # no overlapping case if i < s or i > e: return # reached leaf node if s == e: tree[index].l = val tree[index].sl = INT_MIN return # partial overlap mid = (s + e) // 2 # left subtree call update(tree, 2 * index, s, mid, i, val) # right subtree call update(tree, 2 * index + 1, mid + 1, e, i, val) # largest of ( left.l, right.l) tree[index].l = max(tree[2 * index].l, tree[2 * index + 1].l) # compute second largest # second largest will be # minimum of maximum from left and right node tree[index].sl = min(max(tree[2 * index].l, tree[2 * index + 1].sl), max(tree[2 * index + 1].l, tree[2 * index].sl)) # Function to build the treedef buildtree(tree, a, index, s, e): # tree is build bottom to up if s > e: return # leaf node if s == e: tree[index].l = a[s] tree[index].sl = INT_MIN return mid = (s + e) // 2 # calling the left node buildtree(tree, a, 2 * index, s, mid) # calling the right node buildtree(tree, a, 2 * index + 1, mid + 1, e) # largest of ( left.l, right.l) largest = max(tree[2 * index].l, tree[2 * index + 1].l) # compute second largest # second largest will be minimum # of maximum from left and right node second_largest = min(max(tree[2 * index].l, tree[2 * index + 1].sl), max(tree[2 * index + 1].l, tree[2 * index].sl)) # storing the largest and # second_largest values in the current node tree[index].l = largest tree[index].sl = second_largest# Driver Code# your code goes heren = 5a = [1, 3, 4, 2, 5]# allocating memory for segment treetree = [0]*(4*n + 1)for i in range(4*n + 1): tree[i] = segment(0, 0) # buildtree(tree, a, index, start, end)buildtree(tree, a, 1, 0, n - 1)# query section# storing the resulting noderes = query(tree, 1, 0, n - 1, 0, 2)print("Maximum product in the range 0 and 2 before update: ", (res.l * res.sl))# update section# update(tree, index, start, end, i, v)update(tree, 1, 0, n - 1, 1, 6)res = query(tree, 1, 0, n - 1, 0, 2)print("Maximum product in the range 0 and 2 after update: ", (res.l * res.sl))# The code is contributed by Nidhi goel. |
C#
using System;class Program { static int INT_MAX = 2147483647; static int INT_MIN = -2147483648; // structure defined class segment { // l for largest // sl for second largest public int l; public int sl; public segment(int l, int sl) { this.l = l; this.sl = sl; } } // function to perform queries static segment query(segment[] tree, int index, int s, int e, int qs, int qe) { segment res = new segment(0, 0); res.l = -1; res.sl = -1; // no overlapping case if (qs > e || qe < s || s > e) { return res; } if (s >= qs && e <= qe) { return tree[index]; } // partial overlap case int mid = (s + e) / 2; // calling left node and right node segment left = query(tree, 2 * index, s, mid, qs, qe); segment right = query(tree, 2 * index + 1, mid + 1, e, qs, qe); // largest of ( left.l, right.l) int largest = Math.Max(left.l, right.l); // compute second largest // second largest will be minimum // of maximum from left and right node int second_largest = Math.Min(Math.Max(left.l, right.sl), Math.Max(right.l, left.sl)); // store largest and // second_largest in res res.l = largest; res.sl = second_largest; // return the resulting node return res; } // function to update the query static void update(segment[] tree, int index, int s, int e, int i, int val) { // no overlapping case if (i < s || i > e) { return; } // reached leaf node if (s == e) { tree[index].l = val; tree[index].sl = INT_MIN; return; } int mid = (s + e) / 2; // partial overlap update(tree, 2 * index, s, mid, i, val); // right subtree call update(tree, 2 * index + 1, mid + 1, e, i, val); // largest of ( left.l, right.l) tree[index].l = Math.Max(tree[2 * index].l, tree[2 * index + 1].l); // compute second largest // second largest will be // minimum of maximum from left and right node tree[index].sl = Math.Min(Math.Max(tree[2 * index].l, tree[2 * index + 1].sl), Math.Max(tree[2 * index + 1].l, tree[2 * index].sl)); } // Function to build the tree static void buildtree(segment[] tree, int[] a, int index, int s, int e) { // tree is build bottom to up if (s > e) { return; } if (s == e) { tree[index].l = a[s]; tree[index].sl = INT_MIN; return; } int mid = (s + e) / 2; // tree is build bottom to up buildtree(tree, a, 2 * index, s, mid); // calling the right node buildtree(tree, a, 2 * index + 1, mid + 1, e); // largest of ( left.l, right.l) int largest = Math.Max(tree[2 * index].l, tree[2 * index + 1].l); // compute second largest // second largest will be minimum // of maximum from left and right node int second_largest = Math.Min(Math.Max(tree[2 * index].l, tree[2 * index + 1].sl), Math.Max(tree[2 * index + 1].l, tree[2 * index].sl)); // storing the largest and // second_largest values in the current node tree[index].l = largest; tree[index].sl = second_largest; } // Driver Code // your code goes here static void Main(string[] args) { int n = 5; int[] a = { 1, 3, 4, 2, 5 }; // allocating memory for segment tree segment[] tree = new segment[4 * n + 1]; for (int i = 0; i < 4 * n + 1; i++) { tree[i] = new segment(0, 0); } // buildtree(tree, a, index, start, end) buildtree(tree, a, 1, 0, n - 1); // query section // storing the resulting node segment res = query(tree, 1, 0, n - 1, 0, 2); Console.WriteLine( "Maximum product in the range 0 and 2 before update: " + (res.l * res.sl)); // update section // update(tree, index, start, end, i, v) update(tree, 1, 0, n - 1, 1, 6); res = query(tree, 1, 0, n - 1, 0, 2); Console.WriteLine( "Maximum product in the range 0 and 2 after update: " + (res.l * res.sl)); }} |
Javascript
// structure definedclass segment { // l for largest // sl for second largest constructor(l, sl){ this.l = l; this.sl = sl; }} // function to perform queriesfunction query(tree, index, s, e, qs, qe){ let res = new segment(); res.l = -1; res.sl = -1; // no overlapping case if (qs > e || qe < s || s > e) { return res; } // complete overlap case if (s >= qs && e <= qe) { return tree[index]; } // partial overlap case let mid = Math.floor((s + e) / 2); // calling left node and right node let left = query(tree, 2 * index, s, mid, qs, qe); let right = query(tree, 2 * index + 1, mid + 1, e, qs, qe); // largest of ( left.l, right.l) let largest = Math.max(left.l, right.l); // compute second largest // second largest will be minimum // of maximum from left and right node let second_largest = Math.min(Math.max(left.l, right.sl), Math.max(right.l, left.sl)); // store largest and // second_largest in res res.l = largest; res.sl = second_largest; // return the resulting node return res;} // function to update the queryfunction update(tree, index, s, e, i, val){ // no overlapping case if (i < s || i > e) { return; } // reached leaf node if (s == e) { tree[index].l = val; tree[index].sl = Number.MIN_VALUE; return; } // partial overlap let mid = Math.floor((s + e) / 2); // left subtree call update(tree, 2 * index, s, mid, i, val); // right subtree call update(tree, 2 * index + 1, mid + 1, e, i, val); // largest of ( left.l, right.l) tree[index].l = Math.max(tree[2 * index].l, tree[2 * index + 1].l); // compute second largest // second largest will be // minimum of maximum from left and right node tree[index].sl = Math.min(Math.max(tree[2 * index].l, tree[2 * index + 1].sl), Math.max(tree[2 * index + 1].l, tree[2 * index].sl));} // Function to build the treefunction buildtree(tree, a, index, s, e){ // tree is build bottom to up if (s > e) { return; } // leaf node if (s == e) { tree[index].l = a[s]; tree[index].sl = Number.MIN_VALUE; return; } let mid = Math.floor((s + e) / 2); // calling the left node buildtree(tree, a, 2 * index, s, mid); // calling the right node buildtree(tree, a, 2 * index + 1, mid + 1, e); // largest of ( left.l, right.l) let largest = Math.max(tree[2 * index].l, tree[2 * index + 1].l); // compute second largest // second largest will be minimum // of maximum from left and right node let second_largest = Math.min(Math.max(tree[2 * index].l, tree[2 * index + 1].sl), Math.max(tree[2 * index + 1].l, tree[2 * index].sl)); // storing the largest and // second_largest values in the current node tree[index].l = largest; tree[index].sl = second_largest;} // Driver Code// your code goes herelet n = 5;let a = [ 1, 3, 4, 2, 5 ];// allocating memory for segment treelet tree = new Array(4*n + 1);for(let i = 0; i < 4*n + 1; i++){ tree[i] = new segment();}// buildtree(tree, a, index, start, end)buildtree(tree, a, 1, 0, n - 1);// query section// storing the resulting nodelet res = query(tree, 1, 0, n - 1, 0, 2);console.log("Maximum product in the range 0 and 2 before update: ", (res.l * res.sl));// update section// update(tree, index, start, end, i, v)update(tree, 1, 0, n - 1, 1, 6);res = query(tree, 1, 0, n - 1, 0, 2);console.log("Maximum product in the range 0 and 2 after update: ", (res.l * res.sl));// The code is contributed by Nidhi goel. |
Time Complexity: O(log N) per query and O(N) for building the tree.
Related Topic: Segment Tree
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
