Sorting: Given an array, you need to check if it has contiguous integers

Problem Statement:

Given an array that has duplicate elements,

You need to check if the array has continuous integers.

Example:

Input = [5, 4, 3, 3, 2, ,2 , 6]

Output: Yes

Continuous elements: 2, 3, 4, 5, 6

Solution 1: Sorting

1. Sort the array

2. subtract the value at current index and the previous index, and if the value is greater than 1, return false.

3. else return true at the end

Time Complexity: O(nlogn)
Space Complexity: O(1)

Code Solution

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>

using namespace std;


bool solution(int arr[], int n)
{
    
    sort(arr, arr+n);
    
    for (int i = 1; i < n; i++)
        if (arr[i] - arr[i-1] > 1)
            return false;
    
    return true; 
}

int main()
{
    int arr[] = { 5, 2, 3, 6,
                     4, 4, 6, 6 };
    int n = sizeof(arr) / sizeof(arr[0]);
    
    if (solution(arr, n))
        cout << "Yes";
    
    else
        cout << "No";
    
    return 0;
}

Output

Yes