10 March 2015
Problem overview
Given a list of integers, e.g.: {9,5,2,1,1,0,1,4,6,7}
Write an algorithm to find the longest subset in which the difference between the minimum and maximum numbers is 0 or 1. The subset can have a length of 0 and can hold any of the values in the original array (order doesn't matter).
Algorithm analysis
Using a sliding window mechanism, starting with a min and max, it's possible to keep track of the min and max found so far while calculating the cases when the difference is 0 or 1. There is just one edge case which is when diff = 2, In this case we need to get back to a previous position in order to avoid advancing the window further and forgetting about potential better solutions.
Code in Java
Below is the code that depicts the idea above:
public static int[] findLongestSubsetDiff1(int[] a){
int i = 0, j = 0, diff = 0, longest = 1, minLongestIndex = 0;
int min = a[0], max = a[0], minIndex = 0, maxIndex = 0, newLongest = 0;
<span class="k">for</span><span class="o">(</span><span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="o">;</span> <span class="n">i</span> <span class="o"><</span> <span class="n">a</span><span class="o">.</span><span class="na">length</span><span class="o">;</span> <span class="n">i</span><span class="o">++)</span> <span class="o">{</span>
<span class="n">max</span> <span class="o">=</span> <span class="n">Math</span><span class="o">.</span><span class="na">max</span><span class="o">(</span><span class="n">a</span><span class="o">[</span><span class="n">i</span><span class="o">],</span> <span class="n">max</span><span class="o">);</span>
<span class="n">min</span> <span class="o">=</span> <span class="n">Math</span><span class="o">.</span><span class="na">min</span><span class="o">(</span><span class="n">min</span><span class="o">,</span> <span class="n">a</span><span class="o">[</span><span class="n">i</span><span class="o">]);</span>
<span class="n">diff</span> <span class="o">=</span> <span class="n">Math</span><span class="o">.</span><span class="na">abs</span><span class="o">(</span><span class="n">max</span> <span class="o">-</span> <span class="n">min</span><span class="o">);</span>
<span class="k">if</span> <span class="o">(</span><span class="n">diff</span> <span class="o">==</span> <span class="mi">1</span> <span class="o">||</span> <span class="n">diff</span> <span class="o">==</span> <span class="mi">0</span><span class="o">)</span> <span class="o">{</span>
<span class="n">maxIndex</span> <span class="o">=</span> <span class="n">i</span><span class="o">;</span>
<span class="n">newLongest</span> <span class="o">=</span> <span class="o">(</span><span class="n">maxIndex</span> <span class="o">-</span> <span class="n">minIndex</span><span class="o">)</span> <span class="o">+</span> <span class="mi">1</span><span class="o">;</span>
<span class="k">if</span> <span class="o">(</span><span class="n">longest</span> <span class="o"><</span> <span class="n">newLongest</span><span class="o">)</span> <span class="o">{</span>
<span class="n">longest</span> <span class="o">=</span> <span class="n">newLongest</span><span class="o">;</span>
<span class="n">minLongestIndex</span> <span class="o">=</span> <span class="n">minIndex</span><span class="o">;</span>
<span class="o">}</span>
<span class="o">}</span> <span class="k">else</span> <span class="k">if</span> <span class="o">(</span><span class="n">diff</span> <span class="o">==</span> <span class="mi">2</span><span class="o">)</span> <span class="o">{</span>
<span class="n">minIndex</span> <span class="o">=</span> <span class="n">minLongestIndex</span> <span class="o">+</span> <span class="mi">1</span><span class="o">;</span>
<span class="n">min</span> <span class="o">=</span> <span class="n">a</span><span class="o">[</span><span class="n">minIndex</span><span class="o">];</span>
<span class="n">maxIndex</span> <span class="o">=</span> <span class="n">i</span><span class="o">;</span>
<span class="n">max</span> <span class="o">=</span> <span class="n">a</span><span class="o">[</span><span class="n">i</span><span class="o">];</span>
<span class="n">diff</span> <span class="o">=</span> <span class="n">Math</span><span class="o">.</span><span class="na">abs</span><span class="o">(</span><span class="n">max</span> <span class="o">-</span> <span class="n">min</span><span class="o">);</span>
<span class="k">while</span> <span class="o">(</span><span class="n">diff</span> <span class="o">==</span> <span class="mi">2</span> <span class="o">&&</span> <span class="n">minIndex</span> <span class="o"><</span> <span class="n">maxIndex</span><span class="o">)</span> <span class="o">{</span>
<span class="n">minIndex</span><span class="o">++;</span>
<span class="n">min</span> <span class="o">=</span> <span class="n">a</span><span class="o">[</span><span class="n">minIndex</span><span class="o">];</span>
<span class="n">diff</span> <span class="o">=</span> <span class="n">Math</span><span class="o">.</span><span class="na">abs</span><span class="o">(</span><span class="n">a</span><span class="o">[</span><span class="n">i</span><span class="o">]</span> <span class="o">-</span> <span class="n">min</span><span class="o">);</span>
<span class="o">}</span>
<span class="n">max</span> <span class="o">=</span> <span class="n">Math</span><span class="o">.</span><span class="na">max</span><span class="o">(</span><span class="n">max</span><span class="o">,</span> <span class="n">min</span><span class="o">);</span>
<span class="o">}</span>
<span class="k">else</span> <span class="o">{</span>
<span class="n">min</span> <span class="o">=</span> <span class="n">max</span> <span class="o">=</span> <span class="n">a</span><span class="o">[</span><span class="n">i</span><span class="o">];</span>
<span class="n">minIndex</span> <span class="o">=</span> <span class="n">maxIndex</span> <span class="o">=</span> <span class="n">i</span><span class="o">;</span>
<span class="o">}</span>
<span class="o">}</span>
<span class="kt">int</span><span class="o">[]</span> <span class="n">r</span> <span class="o">=</span> <span class="k">new</span> <span class="kt">int</span><span class="o">[</span><span class="n">longest</span><span class="o">];</span>
<span class="k">for</span><span class="o">(</span><span class="n">j</span><span class="o">=</span><span class="mi">0</span><span class="o">,</span> <span class="n">i</span> <span class="o">=</span> <span class="n">minLongestIndex</span><span class="o">;</span> <span class="n">i</span> <span class="o"><</span> <span class="n">a</span><span class="o">.</span><span class="na">length</span> <span class="o">&&</span> <span class="n">j</span> <span class="o"><</span> <span class="n">longest</span><span class="o">;</span> <span class="n">i</span><span class="o">++,</span> <span class="n">j</span><span class="o">++)</span> <span class="o">{</span>
<span class="n">r</span><span class="o">[</span><span class="n">j</span><span class="o">]</span> <span class="o">=</span> <span class="n">a</span><span class="o">[</span><span class="n">i</span><span class="o">];</span>
<span class="o">}</span>
<span class="k">return</span> <span class="n">r</span><span class="o">;</span>
<span class="o">}</span></code></pre></figure>
Sample test cases:
- {1, 5, 6, 6, 6, 7, 7, 9}
- {9, 7, 7, 6, 5, 4, 4, 2}
- {4, 4, 2, 6, 1, 3, 2, 3,4,4,4,4,5,6,7,8}