title: Find the longest subarray that contains a majority element
body: <p>I am trying to solve this algorithmic problem:</p>
  
  <p><a href="https://dunjudge.me/analysis/problems/469/" rel="noreferrer">https://dunjudge.me/analysis/problems/469/</a></p>
  
  <p>For convenience, I have summarized the problem  statement below.</p>
  
  <blockquote>
    <p>Given an array of length (&lt;= 2,000,000) containing integers in the range [0, 1,000,000], find the
    longest <strong>subarray</strong> that contains a majority element.</p>
    
    <p>A majority element is defined as an element that occurs > floor(n/2) times in a list of length n.</p>
    
    <p>Time limit: 1.5s</p>
    
    <p>For example:</p>
    
    <p>If the given array is [1, 2, 1, 2, 3, 2],</p>
    
    <p>The answer is 5 because the subarray [2, 1, 2, 3, 2] of length 5 from position 1 to 5 (0-indexed) has the number 2 which appears 3 > floor(5/2) times. Note that we cannot take the entire array because 3 = floor(6/2).</p>
  </blockquote>
  
  <p><hr/>
  <strong>My attempt:</strong></p>
  
  <p>The first thing that comes to mind is an obvious brute force (but correct) solution which fixes the start and end indexes of a subarray and loop through it to check if it contains a majority element. Then we take the length of the longest subarray that contains a majority element. This works in O(n^2) with a small optimization. Clearly, this will not pass the time limit.</p>
  
  <p>I was also thinking of dividing the elements into buckets that contain their indexes in sorted order.</p>
  
  <p>Using the example above, these buckets would be:</p>
  
  <p>1: 0,  2</p>
  
  <p>2: 1, 3, 5</p>
  
  <p>3: 4</p>
  
  <p>Then for each bucket, I would make an attempt to merge the indexes together to find the longest subarray that contains k as the majority element where k is the integer label of that bucket.
  We could then take the maximum length over all values of k. I didn't try out this solution as I didn't know how to perform the merging step.
  <hr/>
  Could someone please advise me on a better approach to solve this problem?</p>
  
  <p><strong>Edit:</strong></p>
  
  <p>I solved this problem thanks to the answers of PhamTrung and hk6279. Although I accepted the answer from PhamTrung because he first suggested the idea, I <strong>highly recommend</strong> looking at the answer by hk6279 because his answer elaborates the idea of PhamTrung and is much more detailed (and also comes with a nice formal proof!).</p>