Single Element in a Sorted Array. Find the element that appears once in a sorted array where every other element appears twice.
Given a sorted array of integers. In this array, every element appears twice except one element which appears only once. Write a code to find the element which appears only once.
For example:
Example 1:
Input: [1, 1, 2, 2, 3, 4, 4, 7, 7]
Output: 3
Except 3 every other element appears twice.
Example 2:
Input: [1, 1, 2, 2, 3, 3, 4, 5, 5]
Output: 4
NOTE – Try to solve this problem in O(logn) time complexity and by using constant space O(1).
In this tutorial, I am going to discuss multiple approaches with their time and space complexity to solve this problem.
I have also added the link of a video tutorial at the end of this post.
Single Element in a Sorted Array Video Tutorial
Find element that appears once in a sorted array
Single Element in a Sorted Array
Find the Element that Appears once in a Sorted Array using HashMap
Let’s start with the easiest approach to find the element that appears once in sorted array and rest element appears twice. The easiest approach to solve this problem is by using HashMap.
The idea here is to create a map of element and it’s count. Once we know the count of each number of an array, we can easily find the number which appear only once in an array.
The time complexity of this approach is O(n) and it’s space complexity is also O(n).
Find first non-repeating character in a string
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 |
/* Find the number which occur only once in an array using HashMap */ public class ElementAppearOnce { public static int singleNonDuplicateUsingMap(int[] arr) { int res = 0; //Declare a map Map<Integer, Integer> countMap = new HashMap<>(); //Traverse an array and create a key and value pair for(int i = 0 ; i < arr.length; i++) { countMap.put(arr[i], countMap.getOrDefault(arr[i], 0) + 1); } /* Traverse a map and check the number which occur only once */ for(Map.Entry<Integer, Integer> entry : countMap.entrySet()) { if(entry.getValue() == 1) { res = entry.getKey(); break; } } return res; } public static void main(String[] args) { int[] arr = {1, 1, 2, 2, 3, 3, 4, 5, 5}; int result = singleNonDuplicateUsingMap(arr); System.out.println(result); } } |
Find Element that Appears Once in a Sorted Array using Single Traversal
Let’s improve our previous solution. In our previous approach, we have used extra space to solve this problem.
We can solve this problem simply by traversing an array and compare the element present at i index with i+1 index.
If the element present at both the indexes are same then increment the index by 2. If this condition fails, it means this element has occurred only once. Return this number.
The time complexity of this approach is O(n) and it’s space complexity is O(1).
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
//Traverse an array to find the number which appears only once public int singleNonDuplicateUsingTraversal(int[] nums) { if(nums.length == 0) { return -1; } if(nums.length == 1) { return nums[0]; } int i = 0; while(i < nums.length-1) { if(nums[i] != nums[i+1]) { return nums[i]; } i = i + 2; } return nums[i]; } |
Find Single Element in a Sorted Array using XOR – Java Code
In this example, we are using the property of XOR.
* XOR (Exclusive or) of a number with itself is zero.
For example:
1 ^ 1 = 0
2 ^ 2 =0
* XOR of a number with zero is number itself.
For example:
3 ^ 0 = 3
2 ^ 0 = 2
Using this approach the number which appears twice is cancelled out when we do the XOR. So, At the end we get the number which occur only once.
The time complexity of this approach is O(n) and it’s space complexity is O(1).
Find Single Element in a Sorted Array using XOR
Find next greater element in an array
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
/* Find the Element that Appears once in a Sorted Array using constant space. */ public class ElementAppearOnce { public static int singleNonDuplicateUsingXor(int[] arr) { int res = 0; for(int i: arr) { res ^= i; } return res; } public static void main(String[] args) { int[] arr = {1, 1, 2, 2, 3, 3, 4, 5, 5}; int result = singleNonDuplicateUsingXor(arr); System.out.println(result); } } |
Find Single Element in a Sorted Array using Binary Search – Java Code
Let’s discuss how we can find the element that appears once in sorted array and rest element appears twice using binary search.
Programming questions on Binary Search
We know each element appears twice except one element. All the element has their first occurrence at even index and second occurrence is at odd index. Based on this observation we can use the binary search to solve this problem.
The time complexity of this approach is O(logn) and it’s space complexity is O(1).
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 |
//Using binary search public static int findElementUsingBinarySearch(int[] arr) { //Initial value of start and end variable int start = 0; int end = arr.length - 1; //Run a loop while start is less than end while (start <= end) { //compute mid int mid = (start + end) / 2; //If start is equal to end if (start == end) { //Return the element which appear only once return arr[start]; //If mid is odd } else if (mid % 2 != 0) { /* If value present at mid and mid-1 is equal then search at right half of the array else left half of the array. */ if (arr[mid - 1] == arr[mid]) { start = mid + 1; } else { end = mid - 1; } } else { //If mid is even if (arr[mid] == arr[mid + 1]) { start = mid + 2; } else { end = mid; } } } return -1; } |
