Given an array, arr[] representing a permutation of first N natural numbers in the range [1, N], the task for each ith index is to check if an i-length subarray exists or not such that it contains all the numbers in the range [1, i].
Note: 1 – based indexing used.
Examples:
Input: arr[] = {4, 5, 1, 3, 2}
Output: True False True False True
Explanation:
For i = 1, the subarray {arr[2]} contains all the numbers from [1, i] and of size i(=1). Therefore, the required output is true.
For i = 2, no subarray of size 2 exists which contains all the numbers in the range[1, i]. Therefore, the required output is false.
For i = 3, the subarray {arr[2], arr[3], arr[4]} contains all the numbers from [1, i] and of size i(=3). Therefore, the required output is true.
For i = 4, no subarray of size 4 exists which contains all the numbers in the range[1, i]. Therefore, the required output is false.
For i = 5, the subarray {arr[0], arr[1], arr[2], arr[3], arr[4]} contains all the numbers from [1, i] and of size i(=5). Therefore, the required output is true.Input: arr = {1, 4, 3, 2}
Output: True False False True
Naive Approach: The idea is to traverse the array and for each index, check if there is a subarray of size i which contains all the numbers in the range [1, i] or not. If found to be true, then print True. Otherwise, print False.
Time Complexity: O(N2)
Auxiliary Space: O(N)
Efficient Approach: The problem can be solved using Hashing to store the position of each element of the given array efficiently. Follow the steps below to solve the problem:
- Create a map, say, Map, to store the position of each element of the given array.
- Traverse the array and store the position of each element of the array onto Map.
- Create a set, say st to store the indexes of each element from the range [1, N].
- Initialize two variables, say Min and Max, to store the smallest and the largest elements present in st.
- Iterate over the range [1, N] and insert the value of Map[i] into st and check if Max – Min + 1 = i or not. If found to be true, then print True.
- Otherwise, print False.
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 if a subarray of size i exists// that contain all the numbers in the range [1, i]void checksubarrayExist1_N(int arr[], int N){ // Store the position // of each element of arr[] unordered_map<int, int> pos; // Traverse the array for (int i = 0; i < N; i++) { // Insert the position // of arr[i] pos[arr[i]] = i; } // Store position of each element // from the range [1, N] set<int> st; // Iterate over the range [1, N] for (int i = 1; i <= N; i++) { // Insert the index of i into st st.insert(pos[i]); // Find the smallest element of st int Min = *(st.begin()); // Find the largest element of st int Max = *(st.rbegin()); // If distance between the largest // and smallest element of arr[] // till i-th index is equal to i if (Max - Min + 1 == i) { cout << "True "; } else { cout << "False "; } }}// Driver Codeint main(){ int arr[] = { 1, 4, 3, 2 }; int N = sizeof(arr) / sizeof(arr[0]); checksubarrayExist1_N(arr, N);} |
Java
// Java program to implement// the above approachimport java.util.*;class GFG { // Function to check if a subarray of size i exists // that contain all the numbers in the range [1, i] static void checksubarrayExist1_N(int arr[], int N) { // Store the position // of each element of arr[] Map<Integer, Integer> pos=new HashMap<>(); // Traverse the array for (int i = 0; i < N; i++) { // Insert the position // of arr[i] pos.put(arr[i],i); } // Store position of each element // from the range [1, N] Set<Integer> st=new HashSet<>(); // Iterate over the range [1, N] for (int i = 1; i <= N; i++) { // Insert the index of i into st st.add(pos.get(i)); // Find the smallest element of st int Min = Collections.min(st); // Find the largest element of st int Max = Collections.max(st); // If distance between the largest // and smallest element of arr[] // till i-th index is equal to i if (Max - Min + 1 == i) { System.out.print("True "); } else { System.out.print("False "); } } } // Driver code public static void main(String[] args) { int arr[] = { 1, 4, 3, 2 }; int N = arr.length; checksubarrayExist1_N(arr, N); }}// This code is contributed by offbeat |
Python3
# Python3 program to implement# the above approach# Function to check if a subarray of size i exists# that contain all the numbers in the range [1, i]def checksubarrayExist1_N(arr, N): # Store the position # of each element of arr[] pos = {} # Traverse the array for i in range(N): # Insert the position # of arr[i] pos[arr[i]] = i # Store position of each element # from the range [1, N] st = {} # Iterate over the range [1, N] for i in range(1, N + 1): # Insert the index of i into st st[pos[i]] = 1 # Find the smallest element of st Min = sorted(list(st.keys()))[0] # Find the largest element of st Max = sorted(list(st.keys()))[-1] # If distance between the largest # and smallest element of arr[] # till i-th index is equal to i if (Max - Min + 1 == i): print("True", end = " ") else: print("False", end = " ")# Driver Codeif __name__ == '__main__': arr = [1, 4, 3, 2] N = len(arr) checksubarrayExist1_N(arr, N) # This code is contributed by mohit kumar 29. |
C#
// C# program to implement// the above approachusing System;using System.Collections.Generic;using System.Linq;class GFG{// Function to check if a subarray of size i exists// that contain all the numbers in the range [1, i]static void checksubarrayExist1_N(int[] arr, int N){ // Store the position // of each element of arr[] Dictionary<int, int> pos = new Dictionary<int, int>(); // Traverse the array for(int i = 0; i < N; i++) { // Insert the position // of arr[i] pos[arr[i]] = i; } // Store position of each element // from the range [1, N] HashSet<int> st = new HashSet<int>(); // Iterate over the range [1, N] for(int i = 1; i <= N; i++) { // Insert the index of i into st st.Add(pos[i]); // Find the smallest element of st int Min = st.Min(); // Find the largest element of st int Max = st.Max(); // If distance between the largest // and smallest element of arr[] // till i-th index is equal to i if (Max - Min + 1 == i) { Console.Write("True "); } else { Console.Write("False "); } }}// Driver codepublic static void Main(string[] args){ int[] arr = { 1, 4, 3, 2 }; int N = arr.Length; checksubarrayExist1_N(arr, N);}}// This code is contributed by ukasp |
Javascript
<script>// JavaScript program for the above approach // Function to check if a subarray of size i exists // that contain all the numbers in the range [1, i] function checksubarrayExist1_N(arr, N) { // Store the position // of each element of arr[] let pos = new Map(); // Traverse the array for (let i = 0; i < N; i++) { // Insert the position // of arr[i] pos.set(arr[i],i); } // Store position of each element // from the range [1, N] let st=new Set(); // Iterate over the range [1, N] for (let i = 1; i <= N; i++) { // Insert the index of i into st st.add(pos.get(i)); // Find the smallest element of st let Min = Math.min(...st); // Find the largest element of st let Max = Math.max(...st); // If distance between the largest // and smallest element of arr[] // till i-th index is equal to i if (Max - Min + 1 == i) { document.write("True "); } else { document.write("False "); } } }// Driver Code let arr = [ 1, 4, 3, 2 ]; let N = arr.length; checksubarrayExist1_N(arr, N); </script> |
True False False True
Time Complexity: O(N * log(N))
Auxiliary Space: O(N)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
