Given an array Arr of N integers(duplicates allowed). Print “Yes” if it is a set of contiguous integers else print “No”.
Examples:
Input: Arr = { 5, 2, 3, 6, 4, 4, 6, 6 }
Output: Yes
The elements of array form a contiguous set of integers which is {2, 3, 4, 5, 6} so the output is Yes.
Input: Arr = { 10, 14, 10, 12, 12, 13, 15 }
Output: No
Approach:
- A similar approach is discussed here. It is recommended to go through it before moving further with this article.
- Find the max and min elements from the array.
- Update the array with the difference from the max element in the array.
- Traverse the array and do the following
- If 0 <= abs(arr[i])-1) < n and arr[abs(arr[i])-1)] > 0 means the element is positive (visited first time), make it negative by doing arr[abs(arr[i])-1] = -arr[abs(arr[i])-1].
- Else continue loop means either the value is already visited or out of range of the array
- Traverse the loop again and check if any element is positive means element has a difference greater than 1
break the loop and print “NO” - If no element is found positive, print “YES”
Below is the implementation code:
C++
// C++ program to check if // array contains contiguous // integers with duplicates // allowed in O(1) space #include <bits/stdc++.h> using namespace std; // Function to return true or // false bool check( int arr[], int n) { int k = INT_MIN; int r = INT_MAX; // To find the max and min // in the array for ( int i = 0; i < n; i++) { k = max(k, arr[i]); r = min(r, arr[i]); } k += 1; // Update the array with // the difference from // the max element for ( int i = 0; i < n; i++) arr[i] = k - arr[i]; for ( int i = 0; i < n; i++) { // if the element is positive // and less than the size of // array(in range), make it negative if ( abs (arr[i]) - 1 < n && arr[ abs (arr[i]) - 1] > 0) { arr[ abs (arr[i]) - 1] = -arr[ abs (arr[i]) - 1]; } } int flag = 0; // Loop from 0 to end of the array for ( int i = 0; i <= k - r - 1; i++) { // Found positive, out of range if (arr[i] > 0) { flag = 1; break ; } } return flag == 0; } // Driver function int main() { // Given array int arr[] = { 5, 2, 3, 6, 4, 4, 6, 6 }; int n = sizeof (arr) / sizeof (arr[0]); // Function Calling if (check(arr, n)) cout << "Yes" ; else cout << "No" ; return 0; } |
Java
// Java program to check if array contains // contiguous integers with duplicates // allowed in O(1) space import java.util.*; class GFG { // Function to return true or // false static boolean check( int arr[], int n) { int k = Integer.MIN_VALUE; int r = Integer.MAX_VALUE; // To find the max and min // in the array for ( int i = 0 ; i < n; i++) { k = Math.max(k, arr[i]); r = Math.min(r, arr[i]); } k += 1 ; // Update the array with // the difference from // the max element for ( int i = 0 ; i < n; i++) arr[i] = k - arr[i]; for ( int i = 0 ; i < n; i++) { // if the element is positive // and less than the size of // array(in range), make it negative int abs_value = Math.abs(arr[i]); if (abs_value - 1 < n && arr[abs_value - 1 ] > 0 ) { arr[abs_value - 1 ] = -arr[abs_value - 1 ]; } } int flag = 0 ; // Loop from 0 to end of the array for ( int i = 0 ; i <= k - r - 1 ; i++) { // Found positive, out of range if (arr[i] > 0 ) { flag = 1 ; break ; } } return flag == 0 ; } // Driver function public static void main(String []args) { // Given array int arr[] = { 5 , 2 , 3 , 6 , 4 , 4 , 6 , 6 }; int n = arr.length; // Function Calling if (check(arr, n)) System.out.println( "Yes" ); else System.out.println( "No" ); } } // This code is contributed by Surendra_Gangwar |
Python3
# Python3 program to check if array contains # contiguous integers with duplicates allowed # in O(1) space # Function to return true or false def check(arr, n): k = - 10 * * 9 r = 10 * * 9 # To find the max and min in the array for i in range (n): k = max (k, arr[i]) r = min (r, arr[i]) k + = 1 # Update the array with the difference # from the max element for i in range (n): arr[i] = k - arr[i] for i in range (n): # if the element is positive # and less than the size of # array(in range), make it negative if ( abs (arr[i]) - 1 < n and arr[ abs (arr[i]) - 1 ] > 0 ): arr[ abs (arr[i]) - 1 ] = - arr[ abs (arr[i]) - 1 ] flag = 0 # Loop from 0 to end of the array for i in range (k - r): # Found positive, out of range if (arr[i] > 0 ): flag = 1 break return flag = = 0 # Driver Code # Given array arr = [ 5 , 2 , 3 , 6 , 4 , 4 , 6 , 6 ] n = len (arr) # Function Calling if (check(arr, n)): print ( "Yes" ) else : print ( "No" ) # This code is contributed by Mohit Kumar |
C#
// C# program to check if array contains // contiguous integers with duplicates // allowed in O(1) space using System; class GFG { // Function to return true or // false static bool check( int []arr, int n) { int k = int .MinValue; int r = int .MaxValue; // To find the max and min // in the array for ( int i = 0; i < n; i++) { k = Math.Max(k, arr[i]); r = Math.Min(r, arr[i]); } k += 1; // Update the array with // the difference from // the max element for ( int i = 0; i < n; i++) arr[i] = k - arr[i]; for ( int i = 0; i < n; i++) { // if the element is positive // and less than the size of // array(in range), make it negative if (Math.Abs(arr[i]) - 1 < n && arr[(Math.Abs(arr[i]) - 1)] > 0) { arr[(Math.Abs(arr[i]) - 1)] = - arr[(Math.Abs(arr[i])) - 1]; } } int flag = 0; // Loop from 0 to end of the array for ( int i = 0; i <= k - r - 1; i++) { // Found positive, out of range if (arr[i] > 0) { flag = 1; break ; } } return flag == 0; } // Driver Code static public void Main () { // Given array int []arr = { 5, 2, 3, 6, 4, 4, 6, 6 }; int n = arr.Length; // Function Calling if (check(arr, n)) Console.Write( "Yes" ); else Console.Write( "No" ); } } // This code is contributed by ajit |
Javascript
<script> // Javascript program to check if // array contains contiguous // integers with duplicates // allowed in O(1) space // Function to return true or // false function check(arr, n) { let k = Number.MIN_VALUE; let r = Number.MAX_VALUE; // To find the max and min // in the array for (let i = 0; i < n; i++) { k = Math.max(k, arr[i]); r = Math.min(r, arr[i]); } k += 1; // Update the array with // the difference from // the max element for (let i = 0; i < n; i++) arr[i] = k - arr[i]; for (let i = 0; i < n; i++) { // if the element is positive // and less than the size of // array(in range), make it negative let abs_value = Math.abs(arr[i]); if (abs_value - 1 < n && arr[abs_value - 1] > 0) { arr[abs_value - 1] = -arr[abs_value - 1]; } } let flag = 0; // Loop from 0 to end of the array for (let i = 0; i <= k - r - 1; i++) { // Found positive, out of range if (arr[i] > 0) { flag = 1; break ; } } return flag == 0; } // Driver function // Given array let arr = [ 5, 2, 3, 6, 4, 4, 6, 6 ]; let n = arr.length; // Function Calling if (check(arr, n)) document.write( "Yes" ); else document.write( "No" ); </script> |
Output:
Yes
Time Complexity:
Space Complexity: Extra Space
Approach 2: Using Hash Set
1. Taken an array arr[] to take input and called CheckContiguous() function.
2. In the CheckContiguous function, first creates an unordered_set to store the elements of the array.
3. It then starts by checking if there is a contiguous sequence of smaller integers than the first element of the array.
4. If yes, it keeps updating the counter variable ‘cnt’ and the current element ‘curr_elem’ until it reaches a number that is not present in the set.
6. Then it checks if there is a contiguous sequence of greater integers than the first element of the array.
7. If yes, it keeps updating the counter variable ‘cnt’ and the current element ‘curr_elem’ until it reaches a number that is not present in the set.
8. Finally, the function returns true if the count of contiguous integers is equal to the size of the set, else it returns false.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h> using namespace std; // Function to check whether the array contains // a set of contiguous integers bool CheckContiguous( int arr[], int n) { // Unordered_set to strore elements unordered_set< int > ust; for ( int i = 0; i < n; i++) ust.insert(arr[i]); int cnt = 1; // counter variable // starting with previous smaller element // of arr[0] int curr_elem = arr[0] - 1; // if 'curr_ele' is present in 'us' while (ust.find(curr_elem) != ust.end()) { // increment counter variable cnt++; // update 'curr_ele" curr_elem--; } // starting with next greater element // of arr[0] curr_elem = arr[0] + 1; // If current element available in the set while (ust.find(curr_elem) != ust.end()) { // increment counter variable cnt++; // update 'curr_elem" curr_elem++; } // returns true if array contains a set of contiguous // integers else returns false return (cnt == ( int )(ust.size())); } // Driver code int main() { // Example taken as input int arr[] = { 5, 2, 3, 6, 4, 4, 6, 6 }; int n = sizeof (arr) / sizeof (arr[0]); if (CheckContiguous(arr, n)) cout << "Yes" ; else cout << "No" ; return 0; } |
Java
import java.util.*; public class Main { // Function to check whether the array contains // a set of contiguous integers public static boolean checkContiguous( int [] arr, int n) { // HashSet to store elements HashSet<Integer> set = new HashSet<>(); for ( int i = 0 ; i < n; i++) set.add(arr[i]); int cnt = 1 ; // counter variable // starting with previous smaller element // of arr[0] int curr_elem = arr[ 0 ] - 1 ; // if 'curr_ele' is present in 'set' while (set.contains(curr_elem)) { // increment counter variable cnt++; // update 'curr_elem" curr_elem--; } // starting with next greater element // of arr[0] curr_elem = arr[ 0 ] + 1 ; // If current element available in the set while (set.contains(curr_elem)) { // increment counter variable cnt++; // update 'curr_elem" curr_elem++; } // returns true if array contains a set of contiguous // integers else returns false return (cnt == set.size()); } // Driver code public static void main(String[] args) { // Example taken as input int [] arr = { 5 , 2 , 3 , 6 , 4 , 4 , 6 , 6 }; int n = arr.length; if (checkContiguous(arr, n)) System.out.println( "Yes" ); else System.out.println( "No" ); } } |
Python3
def check_contiguous(arr, n): # Unordered_set to store elements ust = set (arr) cnt = 1 # counter variable # starting with previous smaller element # of arr[0] curr_elem = arr[ 0 ] - 1 # if 'curr_ele' is present in 'us' while curr_elem in ust: # increment counter variable cnt + = 1 # update 'curr_ele" curr_elem - = 1 # starting with next greater element # of arr[0] curr_elem = arr[ 0 ] + 1 # If current element available in the set while curr_elem in ust: # increment counter variable cnt + = 1 # update 'curr_elem" curr_elem + = 1 # returns true if array contains a set of contiguous # integers else returns false return cnt = = len (ust) # Example taken as input arr = [ 5 , 2 , 3 , 6 , 4 , 4 , 6 , 6 ] n = len (arr) if check_contiguous(arr, n): print ( "Yes" ) else : print ( "No" ) |
C#
using System; using System.Collections.Generic; public class GFG { // Function to check whether the array contains // a set of contiguous integers public static bool CheckContiguous( int [] arr, int n) { // HashSet to store elements HashSet< int > set = new HashSet< int >(); for ( int i = 0; i < n; i++) set .Add(arr[i]); int cnt = 1; // counter variable // starting with previous smaller element // of arr[0] int curr_elem = arr[0] - 1; // if 'curr_ele' is present in 'set' while ( set .Contains(curr_elem)) { // increment counter variable cnt++; // update 'curr_elem" curr_elem--; } // starting with next greater element // of arr[0] curr_elem = arr[0] + 1; // If current element is available in the set while ( set .Contains(curr_elem)) { // increment counter variable cnt++; // update 'curr_elem" curr_elem++; } // returns true if array contains a set of contiguous // integers else returns false return cnt == set .Count; } // Driver code public static void Main( string [] args) { // Example taken as input int [] arr = { 5, 2, 3, 6, 4, 4, 6, 6 }; int n = arr.Length; if (CheckContiguous(arr, n)) Console.WriteLine( "Yes" ); else Console.WriteLine( "No" ); } } |
Javascript
<script> // Function to check whether the array contains // a set of contiguous integers function checkContiguous(arr) { // Set to store elements const set = new Set(arr); let cnt = 1; // counter variable // Starting with the previous smaller element of arr[0] let currElem = arr[0] - 1; // If 'currElem' is present in 'set' while (set.has(currElem)) { // Increment counter variable cnt++; // Update 'currElem' currElem--; } // Starting with the next greater element of arr[0] currElem = arr[0] + 1; // If current element is available in the set while (set.has(currElem)) { // Increment counter variable cnt++; // Update 'currElem' currElem++; } // Returns true if the array contains a set of contiguous // integers else returns false return cnt === set.size; } // Driver code const arr = [5, 2, 3, 6, 4, 4, 6, 6]; if (checkContiguous(arr)) { console.log( "Yes" ); } else { console.log( "No" ); } <script> |
Yes
Time complexity: O(n), where n is the size of the input array.
Space complexity: O(n), as an unordered set to store the elements of the array, which can take up to n space in the worst case.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!