Leetcode: Majority Element II

Difficulty: Medium

Majority Element II

Given an integer array of size n, find all elements that appear more than ⌊n/3⌋ times. The algorithm should run in linear time and in O(1) space.

Runtime Analysis:

Runtime: O(n)

Algorithmic Approach:

This problem can be solved using the Boyer-Moore majority vote algorithm.

Before we are digging into this algorithm, let's see one basic observation:
How many majority elements at most in this problem?
Answer: Two.
Explanation: At most there are 3 elements appear exactly n/3 times. So for more than n/3 times, at most there are 2 elements.

Now we discuss the Moore majority vote algorithm. Quoted from wiki:

"The algorithm is carried out in two steps:

1. Eliminate all elements except one.

Iterating through the array of numbers, maintain a current candidate and a counter initialized to 0. With the current element x in iteration, update the counter and (possibly) the candidate:

If the counter is 0, set the current candidate to x and the counter to 1. If the counter is not 0, increment or decrement the counter based on whether x is the current candidate.

2. Determine if the remaining element is a valid majority element.

With the candidate acquired in step 1, iterate through the array of numbers and count its occurrences. Determine if the result is more than half of the sequence's length. If so, the candidate is the majority. Otherwise, the sequence doesn't contain a majority."

The key idea of this algorithm is "decrement" of the counter when new elements are different from all the current candidates.  This "decrement" operation is to cancel out the elements that do not appear most times in the array. Therefore, after one scan, the candidates are the elements which appear most of the times. The last  step is to check if these candidates are satisfied with the condition of more than n/3 times.

Java Code: 

 public class Solution {





  public List<Integer> majorityElement(int[] nums) {
    if (nums == null || nums.length == 0)
        return new ArrayList<Integer>();
        
    List<Integer> result = new ArrayList<Integer>();
    int number1 = nums[0], number2 = nums[0];
    int count1 = 0, count2 = 0, len = nums.length;
    
    for (int i = 0; i < len; i++) {
        if (nums[i] == number1)
            count1++;
            
        else if (nums[i] == number2)
            count2++;
            
        else if (count1 == 0) {
            number1 = nums[i];
            count1 = 1;
        } 
        
        else if (count2 == 0) {
            number2 = nums[i];
            count2 = 1;
        } 
        
        else {
            count1--;
            count2--;
        }
    }
    
    count1 = 0;
    count2 = 0;
    
    for (int i = 0; i < len; i++) {
        if (nums[i] == number1)
            count1++;
            
        else if (nums[i] == number2)
            count2++;
    }
    
    if (count1 > len / 3)
        result.add(number1);
        
    if (count2 > len / 3)
        result.add(number2);
        
    return result;
}

Consecutive Subsequence

Difficulty: Moderate

12/15/2016: Consecutive Subsequence

Find the number of subsequences in a list whose sum is divisible by Integer K.

Input Format
The first line contains T, the number of testcases.
T testcases follow. Each testcase consists of 2 lines.
The first line contains n and k separated by a single space.
And the second line contains n space separated integers.

Output Format
For each test case, output the number of consecutive subsequences whose sum is divisible by k in a newline.

Constraints
1 ≤ T ≤ 20
1 ≤ n ≤ 106
1 ≤ k ≤ 100
1 ≤ a[i] ≤ 104 

Sample Input

2
5 3
1 2 3 4 1
6 2
1 2 1 2 1 2

Sample Output

4
9

Explanation

For

1 2 3 4 1

there exists, 4 subsequences whose sum is divisible by 3, they are

3
1 2
1 2 3
2 3 4

For

1 2 1 2 1 2

there exists, 9 subsequences whose sum is divisible by 2, they are

2
2
2
1 2 1
1 2 1
1 2 1 2
2 1 2 1
1 2 1 2
2 1 2 1 2

Runtime Analysis:

1 ≤ T ≤ 20 
1 ≤ n ≤ 106 
1 ≤ k ≤ 100 
1 ≤ a[i] ≤ 104 

Taking a look at the constraints,  we have 106 possible inputs per row with 20 possible test cases. This indicates that an O(n) solution would take 2 x 107 possible operations. The average processor (usually assumed to be 2GHz) can do 2 x 109  possible operations per second. However each line of code often takes more than 1 operation to perform, so we often estimate 2 x 108 operations per second (off by factor of 10), which means that, for a linear solution, we can execute our code within 1 second and is most likely a viable solution.

Notice here that a O(n2) solution would take approximately 2 x 1013 operations to complete which would likely take 105 seconds to complete, which will definitely cause a timeout.

Algorithmic Approach:

With all questions related to consecutive sums, this problem revolves around the concept of creating an accumulative sum_array. Each index i in the sum_array is the sum of all values arr[j] where 0 <= j <= i. This just basically means that each element in the sum array is equal to the sum of all values up to and inclusive of the index in the original array. The sum_array takes O(n) to compute.

Sample Array:  [1, 2, 1, 2, 1, 2]
Sum Array:       [1, 3, 4, 6, 7, 9]

Thus, when you subtract 2 entries in the sum_array where i < j:

sum_array[j] - sum_array[i] 

You have computed the sum of the subsequence from i+1 to j in O(1) time. 

However, just knowing about the sum_array is not enough to solve this problem. You need to find every possible subsequence from this array and that is an O(n2) runtime. However, there is a trick! Since we only care about the result of (sum % k), if the modulus of any of the values in the array are ever equal, we know that the subsequence in between must be divisible by k. Thus, we can find the total number of subsequence sums which are divisible by k, by using an array of size k to track how many values result in a remainder of (0, 1, 2 ... k-1). After doing this, we have 2 final steps.

1. Count the values in sum_array which are divisible by k
2. Sum each value in our k-sized array from 1 to arr[i]-1

Find the sum of (1) and (2) and you have your answer!

Java Code:

static long kSub(int k, int[] nums) {
    

    int [] sum = new int[nums.length];
    long count = 0;    
    sum[0] = nums[0];
    
    for(int i = 1; i < nums.length; i++){
        sum[i] = sum[i-1] + nums[i];
    }
    
    int [] kVal = new int[k];
    
    for(int i = 0; i < sum.length; i++){       
        int mod = sum[i] % k;

        if(mod == 0)
            count++;

        count += kVal[mod];
        kVal[mod] += 1;
             
    }
    return count;
}