In this tutorial, I am going to discuss a very interesting problem find N/3 repeated number in an array.
Given an array of size n, Write a code to find all the elements that appear more than n/3 times.
NOTE: We have to solve this problem in linear time and in O(1) space.
Example 1:
Input : [3, 2, 3]
Output: 3
In this example, The size of this array is 3. We have to find all the numbers which occurred more than n/3 where n is the size of the array. The number 3 appears more than 1 times.
Example 2:
Input: [1, 1, 1, 3, 3, 2, 2, 2]
Output:[1, 2]
Majority Element II
This problem is a variation of find majority element in an array.
Before solving this problem, let’s discuss some important points which help us to solve this problem efficiently.
For an array of length n.
i) There can be at most one majority element which is more than n/2 times.
ii) There can be at most two majority elements which are more than n/3 times.
In this post, I am going to discuss three approaches and it’s java code to solve this problem.
Method I – Brute Force Approach
The simplest approach is to use two for loops to find the numbers which appear more than n/3 times.
The time complexity of this approach is O(n^2).
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
//Majority Element II - Brute Force Approach public static List<Integer> majorityElementBruteForce(int[] nums) { int majorityCount = nums.length/3; Set<Integer> result = new HashSet<>(); for(int i = 0; i < nums.length; i++) { int count = 0; for(int j = 0; j < nums.length; j++) { if(nums[i] == nums[j]) { count++; } } if(count > majorityCount) { result.add(nums[i]); } } return new ArrayList<>(result); } |
Majority Element II ( > N/3 Times) using HashMap – Java Code
We can improve the time complexity by using HashMap. The idea here is to traverse an array and count the occurrences of each number. Put the number and it’s count in a HashMap.
Then traverse the map and check all the elements which has count greater n/3.
The time complexity of this approach is O(n) and it’s space complexity is also O(n).
Programming Questions on Arrays
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
//Find numbers which occurred greater than n/3 times public static List<Integer> majorityElementUsingMap(int[] nums) { int majorityCount = nums.length/3; List<Integer> result = new ArrayList<>(); Map<Integer, Integer> map = new HashMap<>(); for(int i = 0; i < nums.length; i++) { map.put(nums[i], map.getOrDefault(nums[i],0)+1); } for(Map.Entry<Integer, Integer> record : map.entrySet()) { if(record.getValue() > majorityCount) { result.add(record.getKey()); } } return result; } |
Find N/3 Repeated Number in O(1) Space – Java Code
In this example, let’s discuss how we can find number which appears more N/3 times in O(1) space. To solve this problem i am using Boyer-Moore majority vote algorithm.
Here i am using the observation that, There can be at most two majority elements which are more than n/3 times.
Boyer-Moore majority vote algorithm finds the majority element if it exists. In this algorithm, first we find the candidate for a majority element. After that we verify it whether this candidate element is the majority element or not.
The time complexity of this approach is O(n) and it’s space complexity is O(1).
Insert Delete GetRandom O(1) Solution
|
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 50 51 52 53 54 55 56 57 58 |
/* Boyer Moore Majority Vote Algorithm for Finding Number which Appears more than N/3 times. */ public static List<Integer> majorityElement(int[] nums) { int count1 = 0; int count2 = 0; Integer candidate1 = null; Integer candidate2 = null; //Traverse an array for(int n : nums) { if(candidate1 != null && candidate1 == n) { count1++; } else if (candidate2 != null && candidate2 == n) { count2++; } else if (count1 == 0) { candidate1 = n; count1++; } else if (count2 == 0) { candidate2 = n; count2++; } else { count1--; count2--; } } /* Once we found the candidate, let's verify it whether it's a majority element or not. */ List<Integer> result = new ArrayList<>(); count1 = 0; count2 =0; for(int n : nums) { if(candidate1 != null && candidate1 == n) { count1++; } if (candidate2 != null && candidate2 == n) { count2++; } } int p = nums.length; if (count1 > p/3) result.add(candidate1); if (count2 > p/3) result.add(candidate2); return result; } |
Get minimum element from stack in O(1)
N/3 Repeat Number InterviewBit Solution – Java
|
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 50 51 52 53 54 55 |
//Interview Bit Solution public class Solution { public int repeatedNumber(final List<Integer> a) { int count1 = 0; int count2 = 0; Integer candidate1 = null; Integer candidate2 = null; for(int n : a) { if(candidate1 != null && candidate1 == n) { count1++; } else if (candidate2 != null && candidate2 == n) { count2++; } else if (count1 == 0) { candidate1 = n; count1++; } else if (count2 == 0) { candidate2 = n; count2++; } else { count1--; count2--; } } List<Integer> result = new ArrayList<>(); count1 = 0; count2 =0; for(int n : a) { if(candidate1 != null && candidate1 == n) { count1++; } if (candidate2 != null && candidate2 == n) { count2++; } } int p = a.size(); if (count1 > p/3) result.add(candidate1); if (count2 > p/3) result.add(candidate2); return result.size() > 0 ? result.get(0) : -1; } } |
