Second Smallest Element in an Array

Determining the smallest element of an array is straightforward. Finding the second smallest element as well could be done with two passes of bubble sort, since after \(k\) passes the first \(k\) elements are already in their correct place, but that modifies the original array. The following is a derivation of an alternative algorithm that leaves the array untouched.

Let the array be \(a_1, a_2, ..., a_n\) and let \(\mathbf{m}_1\) and \(\mathbf{m}_2\) denote the smallest and the second smallest element, such that \(\mathbf{m}_1\leq\mathbf{m}_2\). Three cases arise for each new element \(a_i\):

• Case 1) \(a_i\leq\mathbf{m}_1\leq\mathbf{m}_2\)
• Case 2) \(\mathbf{m}_1\leq a_i\leq\mathbf{m}_2\)
• Case 3) \(\mathbf{m}_1\leq\mathbf{m}_2\leq a_i\)

\(\mathbf{m}_1\) and \(\mathbf{m}_2\) are updated while linearly scanning through the array, treating \(\mathbf{m}\) like a small FIFO that new elements are pushed onto the front of. An implementation then looks as follows:

m_1 = min(a_1, a_2)
m_2 = max(a_1, a_2)

for i = 3:n
  if a_i <= m_1
    m_2 = m_1
    m_1 = a_i
  else if a_i <= m_2
    m_2 = a_i
  end
end

Third Smallest Element in Array

The idea generalizes to an arbitrary number of top elements, though the overall complexity grows with each additional element tracked. Letting \(\mathbf{m}_3\) denote the third smallest element gives four cases:

• Case 1) \(a_i\leq\mathbf{m}_1\leq\mathbf{m}_2\leq\mathbf{m}_3\)
• Case 2) \(\mathbf{m}_1\leq a_i\leq\mathbf{m}_2\leq\mathbf{m}_3\)
• Case 3) \(\mathbf{m}_1\leq\mathbf{m}_2\leq a_i\leq\mathbf{m}_3\)
• Case 4) \(\mathbf{m}_1\leq\mathbf{m}_2\leq\mathbf{m}_3\leq a_i\)

Finding the third smallest element in linear time can then be implemented as:

m_1 = min(a_1, a_2, a_3)
m_3 = max(a_1, a_2, a_3)
m_2 = a_1 + a_2 + a_3 - m_1 - m_3

for i = 4:n
  if a_i <= m_1
    m_3 = m_2
    m_2 = m_1
    m_1 = a_i
  else if a_i <= m_2
    m_3 = m_2
    m_2 = a_i
  else if a_i <= m_3
    m_3 = a_i
  end
end

In general, tracking the \(k\) smallest elements this way requires \(k+1\) cases per new element and \(O(k)\) comparisons in the worst case, for an overall running time of \(O(nk)\), without allocating more than \(O(k)\) auxiliary storage or touching the input array.