Robert Eisele
Engineer, Systems Architect and DBA

Second smallest element in array

Determining the smallest element of an array is an easy task. If we want to find the second smallest element, we could use two iterations of bubble-sort, since the first \(k\) elements are at the right place after \(k\) iterations already. This however modifies the original array. The following is a derivation of an alternative algorithm, which does not touch the array.

Let the array be \(a_1, a_2, ..., a_n\) and let \(\mathbf{m}_1\) and \(\mathbf{m}_2\) the smallest and the second smallest element, such that \(\mathbf{m}_1\leq\mathbf{m}_2\). We now can construct three cases:

  • 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\)

What we do now is modifying \(\mathbf{m}_1\) and \(\mathbf{m}_2\) as we linearly go through the array. That is, we move new elements at the top of \(\mathbf{m}\), seeing it as a fifo. An implementation can then look 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 can be extended to an arbitrary number of top elements, but note that the overall complexity increases. However, let \(\mathbf{m}_3\) be the third smallest element, we can then make 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\)

Searching for the third smallest element in linear time can then be implemented like this:

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