Given an array arr[] of length N, the task is to find the number of Good Ranges in the array arr[].
A Good Range is defined as the range of left and right indices, i.e, [L. R] in the array arr[] such that by removing all the numbers in the range [L, R] of the array arr[] and the appearances of those elements outside the range, the array arr[] becomes sorted in non-decreasing order.
Example:
Input: N=3, arr[] = {9, 8, 7}
Output: 3
Explanation: The good ranges are: (2, 3), (1, 3), (1, 2).
(2, 3) is a good range as the resultant array [9] is sorted (we deleted 8, 7).
(1, 3) is a good range as the resultant array [] which is sorted (we deleted 9, 8, 7)
(1, 2) is a good range as the resultant array [7] is sorted (we deleted 9, 8).Input: N=5, arr[] = {5, 3, 1, 5, 2}
Output: 7
Explanation: The good ranges are: (1, 2), (1, 3), (1, 4), (1, 5), (2, 4), (2, 5), (3, 5).
(1, 2) is a good range as the resultant array [1, 2] is sorted
(1, 3) is a good range as the resultant array [2] is sorted
(1, 4) is a good range as the resultant array [2] is sorted
(1, 5) is a good range as the resultant array [] is sorted
(2, 4) is a good range as the resultant array [2] is sorted
(2, 5) is a good range as the resultant array [] is sorted
(3, 5) is a good range as the resultant array [3] is sorted
Approach: The approach is to find every subarray [l, r] and check if the remaining array is sorted or not. If the array is sorted, then, with the left part of the range at l and right part from r to the end, every subarray will be the answer. Below is the implementation of the above approach:
- Initialize the variable count as 0 to store the number of such subarrays.
- Define a function chk_sorted(l, r, a) to check if the remaining array a[] is sorted or not:
- Initialize the list l to store all the elements of the subarray from l to r in the array a[].
- Initialize the array chk[] to store the elements of the array [] which are not present in the range [l, r].
- Iterate over the range [0, N] using variable i and perform the following steps:
- Initialize the list chk1 to store array chk[].
- Sort the list chk1 and check if chk1 is equal to chk, then, return true else, false.
- Iterate over the range [0, N] using variable i and perform the following steps:
- Iterate over the range [i+1, N] using variable i and perform the following steps:
- Call the function chk_sorted(i, j, a) and if the function returns true, then, increase the value of count by len(a)-j and break the loop.
- Iterate over the range [i+1, N] using variable i and perform the following steps:
- Return the value of count as the answer.
Below is the implementation of the above approach.
C++
// C++ program to implement the above approach#include <bits/stdc++.h>using namespace std;// Function to check array is sorted or notbool chk_sorted(int l, int r, vector<int> a){ // Taking range element separately // to be removed vector<int> temp; unordered_set<int> s; for(int i = l; i <= r; i++) { temp.push_back(a[i]); s.insert(a[i]); } vector<int> chk; for(int i = 0; i < a.size(); i++) { // Checking is all range element // occurrence is removed if (s.find(a[i]) == s.end()) { chk.push_back(a[i]); } } vector<int> chk1 = chk; sort(chk1.begin(), chk1.end()); // If array is sorted return true for(int i = 0; i < chk.size(); i++) { if (chk[i] != chk1[i]) { return false; } } return true;}// Function to count all good rangesint countp(vector<int> a){ // Initial count 0 int count = 0; // Nested loop implementation for(int i = 0; i < a.size(); i++) { for(int j = i + 1; j < a.size(); j++) { // Checking if range is good if (chk_sorted(i, j, a)) { // According to observation as given // in approach count += a.size() - j; break; } } } return count;}// Driver codeint main(){ int N = 5; vector<int> A = { 5, 3, 1, 5, 2 }; cout << (countp(A));}// This code is contributed by Potta Lokesh |
Java
// Java program to implement the above approachimport java.util.*;class GFG{// Function to chk array is sorted or notstatic boolean chk_sorted(int l, int r, int []a){ // Taking range element separately // to be removed Vector<Integer> temp = new Vector<Integer>(); HashSet<Integer> s = new HashSet<Integer>(); for(int i = l; i <= r; i++) { temp.add(a[i]); s.add(a[i]); } Vector<Integer> chk=new Vector<Integer>(); for(int i = 0; i < a.length; i++) { // Checking is all range element // occurrence is removed if (!s.contains(a[i])) { chk.add(a[i]); } } Vector<Integer> chk1 = new Vector<Integer>(chk); Collections.sort(chk1); // If array is sorted return true for(int i = 0; i < chk.size(); i++) { if (chk.get(i) != chk1.get(i)) { return false; } } return true;}// Function to count all good rangesstatic int countp(int []a){ // Initial count 0 int count = 0; // Nested loop implementation for(int i = 0; i < a.length; i++) { for(int j = i + 1; j < a.length; j++) { // Checking if range is good if (chk_sorted(i, j, a)) { // According to observation as given // in approach count += a.length - j; break; } } } return count;}// Driver codepublic static void main(String[] args){ int N = 5; int [] A = { 5, 3, 1, 5, 2 }; System.out.print(countp(A));}}// This code is contributed by shikhasingrajput |
Python3
# Python program to implement the above approach# function to chk array is sorted or notdef chk_sorted(l, r, a): # taking range element separately # to be removed l = list(a[l:r + 1]) chk = [] for i in a: # checking is all range element # occurrence is removed if(i not in l): chk.append(i) chk1 = list(chk) chk1.sort() # if array is sorted return true if(chk1 == chk): return True else: return False# function to count all good rangesdef countp(a): # initial count 0 count = 0 # nested loop implementation for i in range(len(a)): for j in range(i + 1, len(a)): # checking if range is good if(chk_sorted(i, j, a)): # according to observation as given # in approach count += len(a)-j break return count# Driver codeN = 5A = [5, 3, 1, 5, 2]print(countp(A)) |
C#
// C# program to implement the above approachusing System;using System.Collections.Generic;class GFG { // Function to chk array is sorted or not static bool chk_sorted(int l, int r, int[] a) { // Taking range element separately // to be removed List<int> temp = new List<int>(); HashSet<int> s = new HashSet<int>(); for (int i = l; i <= r; i++) { temp.Add(a[i]); s.Add(a[i]); } List<int> chk = new List<int>(); for (int i = 0; i < a.Length; i++) { // Checking is all range element // occurrence is removed if (!s.Contains(a[i])) { chk.Add(a[i]); } } List<int> chk1 = new List<int>(chk); chk1.Sort(); // If array is sorted return true for (int i = 0; i < chk.Count; i++) { if (chk[i] != chk1[i]) { return false; } } return true; } // Function to count all good ranges static int countp(int[] a) { // Initial count 0 int count = 0; // Nested loop implementation for (int i = 0; i < a.Length; i++) { for (int j = i + 1; j < a.Length; j++) { // Checking if range is good if (chk_sorted(i, j, a)) { // According to observation as given // in approach count += a.Length - j; break; } } } return count; } // Driver code public static void Main(string[] args) { int[] A = { 5, 3, 1, 5, 2 }; Console.WriteLine(countp(A)); }}// This code is contributed by ukasp. |
Javascript
<script>// JavaScript program to implement the above approach// function to chk array is sorted or notfunction chk_sorted(l, r, a){ // taking range element separately // to be removed l = a.slice(l, r + 1) let chk = [] for (let i of a){ // checking is all range element // occurrence is removed if(!l.includes(i)){ chk.push(i) } } let chk1 = [...chk] chk1.sort() // if array is sorted return true if(chk1.every((val, index) => val == chk[index])) return true else return false}// function to count all good rangesfunction countp(a){ // initial count 0 let count = 0 // nested loop implementation for (let i = 0; i < a.length; i++){ for(let j = i + 1; j < a.length; j++){ // checking if range is good if(chk_sorted(i, j, a)){ // according to observation as given // in approach count += a.length - j break } } } return count}// Driver codelet N = 5let A = [5, 3, 1, 5, 2]document.write(countp(A))</script> |
Output
7
Time Complexity: O(N*N*N)
Auxiliary Space: O(N)
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!
