Given an array of length N containing integers between 1 and N, determine if it contains any duplicates in O(n) time complexity and O(1) space complexity – coding hangover

Given an array of length N containing integers between 1 and N, determine if it contains any duplicates in O(n) time complexity and O(1) space complexity

Since we cannot use extra space, take advantage of the fact that the array has elements only from 1 to n and there are n elements in the array(index ranges from 0 to n-1) So if 1 occurs make value at 0th index negative if 2 occurs make the value at 1st index negative if … Continue reading Given an array of length N containing integers between 1 and N, determine if it contains any duplicates in O(n) time complexity and O(1) space complexity