Find duplicate element in an Array!

Sorting Method

Problem Statement

Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive.

There is only one repeated number in nums, return this repeated number.

Example 1:

Input: nums = [1,3,4,2,2]
Output: 2

Example 2:

Input: nums = [3,1,3,4,2]
Output: 3

Constraints:

• 2 <= n <= 3 * 104
• nums.length == n + 1
• 1 <= nums[i] <= n
• All the integers in nums appear only once except for precisely one integer which appears two or more times.

For detailed description of the question and for submission, refer to this question on Leetcode

Solutions

1. Using Sorting method

Approach-:

Many of you might have already guessed the solution! Right? Yes! just sort the array in ascending order or descending order using C++ STL sort() function. However, if the interviewer asks for a custom sort function you can write your own Merge sort or Heap sort algorithm(Because of better time complexities than other sorting algorithms in worst cases). After sorting, start a loop from index 1…n if ascending , and 0…n-1 if array is sorted in descending order. If any two consecutive elements are found same, return that element as it is duplicate, otherwise the loop finishes and return -1.

Code-:

Analysis-:

Time complexity-: O(n log n)

Space complexity-: O(1)

If we use the sort() function provided by the C++ STL library, then it is important to know that at backend the sorting algorithm using by sort() function is IntroSort.

The algorithm used by sort() is IntroSort. Introsort being a hybrid sorting algorithm uses three sorting algorithm to minimise the running time, Quicksort, Heapsort and Insertion Sort. Simply putting, it is the best sorting algorithm around. It is a hybrid sorting algorithm, which means that it uses more than one sorting algorithms as a routine.

The time complexity of IntroSort algorithm is O(n log n) in worst cases(Better than other sortig algorithms such as Quick Sort or Bubble Sort).

And as we don’t use any extra array or vector in our program, the space complexity of this solution is O(1)

Easy Right? But what if the interviewer asks you optimise the solution and further reduce the time complexity to O(n). Don’t worry sorting is not the last(also, not the best) solution left for this problem. Let’s do what our interviewer has asked us to do.

OPTIMISE IT!!!!

Check out how to solve this question in O(n) time using the Hashing approach!

Stay tuned for future updates!