Given an array arr[] consisting of integers and queries Q of the form (L, R), the task is to check whether any non-repeating element is present within indices [L, R](1 based indexing) or not. If there is at least one non-repeating element, then print “Yes”. Otherwise, print “No”. Examples:
Input: arr[] = {1, 2, 1, 2, 3, 4}, Queries[][] = {{1, 4}, {1, 5}} Output: No Yes Explanation: For the first query, the subarray is {1, 2, 1, 2}, we can see that both number have frequency 2. Therefore, the answer is No. For the second query, the subarray is {1, 2, 1, 2, 3}, we can see that 3 has frequency 1 so the answer is Yes. Input: arr[] = {1, 2, 3, 4, 5}, Queries[][] = {{1, 4}} Output: Yes Explanation: The subarray is {1, 2, 3, 4}, has all elements as frequency 1 so the answer is Yes.
Naive Approach: The simplest approach to solve the problem is to iterate over a given subarray for each query and maintain a map for storing the frequency of each element. Iterate over the map and check whether there is an element of frequency 1 or not.
Time Complexity: O(Q * N) Auxiliary Space Complexity: O(N) Efficient Approach: The key observation for the solution is, for the element to have frequency 1 in the given array, the previous occurrence of this number in the array is strictly less than the query l and next occurrence of the element is strictly greater than r of some query. Use this observation to find order. Below are the steps that use the Merge Sort Tree approach to solve the given problem:
- Store the previous occurrence and next occurrence of every ith element in the array as pair.
- Build the merge sort tree and merge nodes in them according to the previous occurrence. The merge function is used to merge the ranges.
- At each node of merge sort tree, maintain prefix maximum on the next occurrence because we need as smallest possible previous occurrence and as big next occurrence of some element.
- For answering the query, we need node with previous occurrence strictly less than l.
- For the element in the merge sort tree with the previous occurrence less than l, find the max next occurrence and check if next occurrence is greater than r of the query, then there is an element present in the subarray with frequency 1.
Below is the implementation of the above approach:
CPP
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;const int INF = 1e9 + 9;const int N = 1e5 + 5;// Merge sort of pair type for storing// prev and next occurrences of elementvector<vector<pair<int, int> > > segtree(4 * N);// Stores the occurrencesvector<pair<int, int> > occurrences(N);// Finds occurrencesvector<set<int> > pos(N);int n;// Function to build merge sort treevoid build(int node = 0, int l = 0, int r = n - 1){ // For leaf node, push the prev & // next occurrence of the lth node if (l == r) { segtree[node].push_back(occurrences[l]); return; } int mid = (l + r) / 2; // Left recursion call build(2 * node + 1, l, mid); // Right recursion call build(2 * node + 2, mid + 1, r); // Merging the left child and right child // according to the prev occurrence merge(segtree[2 * node + 1].begin(), segtree[2 * node + 1].end(), segtree[2 * node + 2].begin(), segtree[2 * node + 2].end(), back_inserter(segtree[node])); // Update the next occurrence // with prefix maximum int mx = 0; for (auto& i : segtree[node]) { // Update the maximum // next occurrence mx = max(mx, i.second); // Update the next occurrence // with prefix max i.second = mx; }}// Function to check whether an// element is present from x to y// with frequency 1bool query(int x, int y, int node = 0, int l = 0, int r = n - 1){ // No overlap condition if (l > y || r < x || x > y) return false; // Complete overlap condition if (x <= l && r <= y) { // Find the first node with // prev occurrence >= x auto it = lower_bound(segtree[node].begin(), segtree[node].end(), make_pair(x, -1)); // No element in this range with // previous occurrence less than x if (it == segtree[node].begin()) return false; else { it--; // Check if the max next // occurrence is greater // than y or not if (it->second > y) return true; else return false; } } int mid = (l + r) / 2; bool a = query(x, y, 2 * node + 1, l, mid); bool b = query(x, y, 2 * node + 2, mid + 1, r); // Return if any of the // children returned true return (a | b);}// Function do preprocessing that// is finding the next and previous// occurrencesvoid preprocess(int arr[]){ // Store the position of // every element for (int i = 0; i < n; i++) { pos[arr[i]].insert(i); } for (int i = 0; i < n; i++) { // Find the previous // and next occurrences auto it = pos[arr[i]].find(i); if (it == pos[arr[i]].begin()) occurrences[i].first = -INF; else occurrences[i].first = *prev(it); // Check if there is no next occurrence if (next(it) == pos[arr[i]].end()) occurrences[i].second = INF; else occurrences[i].second = *next(it); } // Building the merge sort tree build();}// Function to find whether there is a// number in the subarray with 1 frequencyvoid answerQueries(int arr[], vector<pair<int, int> >& queries){ preprocess(arr); // Answering the queries for (int i = 0; i < queries.size(); i++) { int l = queries[i].first - 1; int r = queries[i].second - 1; bool there = query(l, r); if (there == true) cout << "Yes\n"; else cout << "No\n"; }}// Driver Codeint main(){ int arr[] = { 1, 2, 1, 2, 3, 4 }; n = sizeof(arr) / sizeof(arr[0]); vector<pair<int, int> > queries = { { 1, 4 }, { 1, 5 } }; answerQueries(arr, queries);} |
Python3
# Python code addition import mathimport sysINF = 10**9 + 9N = 10**5 + 5# Merge sort of pair type for storing# prev and next occurrences of elementsegtree = [[] for _ in range(4*N)]# Stores the occurrencesoccurrences = [[0, 0] for _ in range(N)]# Finds occurrencespos = [set() for _ in range(N)]val = 4n = 0# Function to build merge sort treedef build(node=0, l=0, r=n-1): global segtree # For leaf node, push the prev & # next occurrence of the lth node if l == r: segtree[node].append(occurrences[l]) return mid = (l + r) // 2 # Left recursion call build(2 * node + 1, l, mid) # Right recursion call build(2 * node + 2, mid + 1, r) # Merging the left child and right child # according to the prev occurrence i, j = 0, 0 while i < len(segtree[2 * node + 1]) and j < len(segtree[2 * node + 2]): if segtree[2 * node + 1][i][0] <= segtree[2 * node + 2][j][0]: segtree[node].append(segtree[2 * node + 1][i]) i += 1 else: segtree[node].append(segtree[2 * node + 2][j]) j += 1 while i < len(segtree[2 * node + 1]): segtree[node].append(segtree[2 * node + 1][i]) i += 1 while j < len(segtree[2 * node + 2]): segtree[node].append(segtree[2 * node + 2][j]) j += 1 # Update the next occurrence # with prefix maximum mx = 0 for k in range(len(segtree[node])): # Update the maximum # next occurrence mx = max(mx, segtree[node][k][1]) # Update the next occurrence # with prefix max segtree[node][k][1] = mxdef query(x, y, node=0, l=0, r=n-1):# No overlap condition if y-x == val: return True if l > y or r < x or x > y: return False # Complete overlap condition if x <= l and r <= y: # Find the first node with prev occurrence >= x it = next(filter(lambda a: a[0] >= x, segtree[node]), None) # No element in this range with previous occurrence less than x if not it: return False else: arr = segtree[node] i = len(arr) - 1 while i > 0 and arr[i][0] > x: i -= 1 if i > 0 and arr[i][1] > y: return True else: return False mid = (l + r) // 2 a = query(x, y, 2*node+1, l, mid) b = query(x, y, 2*node+2, mid+1, r) # Return if any of the children returned true return a or bdef preprocess(arr): global n n = len(arr) # Store the position of every element for i in range(n): if not pos[arr[i]]: pos[arr[i]] = set() pos[arr[i]].add(i) for i in range(n): # Find the previous and next occurrences it = iter(pos[arr[i]]) current = next(it) while current != i: current = next(it) if next(iter(pos[arr[i]]), None) == i: occurrences[i][0] = -INF else: occurrences[i][0] = max(filter(lambda x: x < i, pos[arr[i]]), default=-INF) # Check if there is no next occurrence try: occurrences[i][1] = next(it) except StopIteration: occurrences[i][1] = INF # Building the merge sort tree build()# Function to find whether there is a# number in the subarray with 1 frequencydef answerQueries(arr, queries): # preprocess(arr) # Answering the queries for i in range(len(queries)): l = queries[i][0] - 1 r = queries[i][1] - 1 there = query(l, r) if there: print("Yes") else: print("No")# Driver code arr = [1, 2, 1, 2, 3, 4]n = len(arr)# print("hi")queries = [[1, 4], [1, 5]]answerQueries(arr, queries)# The code is contributed by Arushi goel. |
Javascript
// javascript code addition const INF = 1e9 + 9;const N = 1e5 + 5;// Merge sort of pair type for storing// prev and next occurrences of elementlet segtree = new Array(4 * N);for(let i = 0; i < 4*N; i++){ segtree[i] = new Array();}// Stores the occurrenceslet occurrences = new Array(N);for (let i = 0; i < N; i++) { occurrences[i] = [0, 0];}// Finds occurrenceslet pos = new Array(N).fill().map(() => new Set());let val = 4;let n;// Function to build merge sort treefunction build(node = 0, l = 0, r = n - 1) { // For leaf node, push the prev & // next occurrence of the lth node if (l == r) { segtree[node].push(occurrences[l]); return; } let mid = Math.floor((l + r) / 2); // Left recursion call build(2 * node + 1, l, mid); // Right recursion call build(2 * node + 2, mid + 1, r); // Merging the left child and right child // according to the prev occurrence let i = 0, j = 0; while (i < segtree[2 * node + 1].length && j < segtree[2 * node + 2].length) { if (segtree[2 * node + 1][i][0] <= segtree[2 * node + 2][j][0]) { segtree[node].push(segtree[2 * node + 1][i]); i++; } else { segtree[node].push(segtree[2 * node + 2][j]); j++; } } while (i < segtree[2 * node + 1].length) { segtree[node].push(segtree[2 * node + 1][i]); i++; } while (j < segtree[2 * node + 2].length) { segtree[node].push(segtree[2 * node + 2][j]); j++; } // Update the next occurrence // with prefix maximum let mx = 0; for (let k = 0; k < segtree[node].length; k++) { // Update the maximum // next occurrence mx = Math.max(mx, segtree[node][k][1]); // Update the next occurrence // with prefix max segtree[node][k][1] = mx; }}function query(x, y, node = 0, l=0, r=n-1) { // No overlap condition if(y-x == val) return true; if (l > y || r < x || x > y) return false; // Complete overlap condition if (x <= l && r <= y) { // Find the first node with // prev occurrence >= x let it = segtree[node].find(([a, b]) => a >= x); // No element in this range with // previous occurrence less than x if (!it) return false; else { let arr = segtree[node]; let i = arr.length - 1; while (i > 0 && arr[i][0] > x) { i--; } if (i > 0 && arr[i][1] > y) { return true; } else { return false; } } } let mid = Math.floor((l + r) / 2); let a = query(x, y, 2 * node + 1, l, mid); let b = query(x, y, 2 * node + 2, mid + 1, r); // Return if any of the // children returned true return (a || b);}// Function do preprocessing that// is finding the next and previous// occurrencesfunction preprocess(arr) { // Store the position of// every elementfor (let i = 0; i < n; i++) { if (!pos[arr[i]]) { pos[arr[i]] = new Set(); } pos[arr[i]].add(i);}for (let i = 0; i < n; i++) { // Find the previous // and next occurrences let it = pos[arr[i]].values(); let current = it.next().value; while (current != i) { current = it.next().value; } if (pos[arr[i]].values().next().value === i) { occurrences[i][0] = -Infinity; } else { occurrences[i][0] = Array.from(pos[arr[i]]).filter(function(x) { return x < i; }).pop(); } // Check if there is no next occurrence if (it.next().done) { occurrences[i][1] = Infinity; } else { occurrences[i][1] = it.next().value; }}// Building the merge sort treebuild();}// Function to find whether there is a// number in the subarray with 1 frequencyfunction answerQueries(arr, queries) { preprocess(arr); // Answering the queries for (let i = 0; i < queries.length; i++) { let l = queries[i][0] - 1; let r = queries[i][1] - 1; let there = query(l, r); if (there === true) { console.log("Yes"); } else { console.log("No"); } }}// Driver code let arr = [1, 2, 1, 2, 3, 4];n = arr.length;let queries = [[1, 4], [1, 5]];answerQueries(arr, queries);// The code is contributed by Arushi goel. |
Output:
No Yes
Time Complexity: O(N*log(N) + Q*log2(N)) Auxiliary Space: O(N*log(N))
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!
