Find largest sub-array formed by consecutive integers

Cool – you can get O(n^2) time here by building the set as you go along in the inner loop that iterates through j. If max – min == j – i, and if all of the values between i and j are distinct (which you can tell from the set size), then you know immediately that the subsequence consists of the consecutive integers in the range [min, max].

You can also break out of the inner loop early if you ever run into a duplicate.

Will think about Dimitriy’s O(n) hint, cool…

O(n) solution in swift – Feel free to test on Xcode 10.0

//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

Logic:

1. Define a dictionary that holds key:value pairs where key = array element & value = element position in array
2. Traverse through the input array
3. If element previously present in dictionary – we know that we have reached a duplicate element
So capture current startIndex and endIndex. If difference between startIndex and endIndex is greater than maximum length seen so far – update the maxStartIndex and maxEndIndex.
4. Increment startIndex to endIndex + 1. This is to start a new subArray excluding the previous array found.
5. Else if element not previously present in dictionary – simply increment the endIndex of the current SubArray under consideration.
6. Insert every new element as we traverse through the array into the dictionary along with its associated array index.
7. Finally print out the maxStartIndex & maxEndIndex to get the start and end index of the maximum subarray of consecutive numbers.

/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

Code:

func findLargestSubArrayOfConsecutiveNumbers(inputArray: [Int]){

/* Handling edge cases like empty Array. You can handle null cases as well */
guard !inputArray.isEmpty else{
print(“Empty Array”)
return
}

/* Declare variables */
var dict = [Int: Int]()
var startIndex = 0
var endIndex = 0
var maxLength = 0
var maxStartIndex = 0
var maxEndIndex = 0

/* Traverse through the array */
for (index, value) in inputArray.enumerated(){

/* If a duplicate is found */
if let recordedIndex = dict[value]{

/* Capture the subArray if and only if it is the maximum length subArray seen so far */
if endIndex – startIndex > maxLength{
maxLength = endIndex – startIndex
maxStartIndex = startIndex
maxEndIndex = endIndex
}

/* Let go of the above sub array and start a new one */
startIndex = recordedIndex + 1

}else{

/* If duplicate not encountered – simply increment end Index */
endIndex = index
}

/* Insert every element of the array encountered into dictionary with its associated index */
dict[value] = index
}

print(“Largest SubArray of Consecutive numbers = [\(maxStartIndex), \(maxEndIndex)]”)
}

/* Call the above method */
findLargestSubArrayOfConsecutiveNumbers(inputArray: [0,0,0,1,2,5,4,1])

A hashmap implementation can bring down the time complexity to O(n) keeping it in-place . Also an approach using merge sot can reduce the algorithm to O(nlogn) but with a space complexity of O(nlogn) . The above question was asked to me in my Facebook interview 🙂

O(n*n) time and Omega(n) space –
http://ideone.com/87Hzjc

https://ideone.com/PhXLY1

True Answer

js in O(n^2)

https://jsbin.com/yedeseyepi/edit?js,console

It seems like visited array is not needed. Isn’t it?

Perhaps, the description to the problem should be to find the largest subarray of consecutive integers that can be formed by arranging the integers in order.

Hi TechieDelight, O(n) solution by mapping numbers to their sequence lengths
https://studynotesallenyuan.wordpress.com/2018/09/24/longest-consecutive-sequence/

Edit: this is for subsequence. Question given is for contiguous subarray

This can be solved in O(n) by storing the element in a map {item -> position} and keeping track of the longest sub-array with no duplicate element. Scan through the array storing {item, position}. if the same element is found capture the current sub-array and update the start index of the next sub array . Take the longest one.

Solution in O(n)

public static void largestUniqueSubArray(int[] arr) {
if (arr.length <= 0)
System.out.println("Invalid input");
HashMap<Integer, Integer> mMap = new HashMap<>();
HashMap<Integer, Integer> indices = new HashMap<>();
int largestSoFar = 1;
int currentLargest = 0;
int startIndex = 0;
for (int i = 0; i < arr.length; i++) {
if (mMap.containsValue(arr[i])) {
largestSoFar = 1;
indices.put(startIndex, i - 1); // start, end of previous subarray
startIndex = i-1;
} else {
mMap.put(i, arr[i]);
largestSoFar++;
if (i == arr.length - 1) {
indices.put(startIndex, i);
}
}
if (currentLargest < largestSoFar) {
currentLargest = largestSoFar;
}
}
int endIndex = 0;
int difference = 0;
for (Integer start : indices.keySet()) {
if (difference < Math.abs(start - indices.get(start))) {
difference = Math.abs(start - indices.get(start));
startIndex = start;
endIndex = indices.get(start);
}
}
System.out.println("The largest subarray was " + currentLargest + " from index: " + startIndex +
" to index: " + endIndex);
System.out.println("Displaying the subarray");
for (int j = startIndex; j <= endIndex; j++) {
System.out.print(arr[j] + " ");
}
}