Wednesday, August 24, 2011

shift array elements to the right in PHP

Another algorithm related question for C/C++ devs. It is always interesting to see how to solve it in PHP.

The question is: implement a function to shift $k array elements to the right. Time complexity must <= O(n)
For example, we have an array $a = array('a', 'b', 'c', 'd', 'e'), a function rightShift($array, $k), and if we call rightShift($a, 2), the return result must be array('c', 'd', 'e', 'a', 'b'). 'a' and 'b' have been shifted to the right of the array.

It is quite simple in PHP, with PHP's array functions.

function rightShift($array, $k)
{
                for($i=0; $i<$k; $i++) {
                                $temp = array_shift($array);
                                array_push($array, $temp);
                }
                return $array;
}

Even without using PHP array function, it is still simple:

function rightShift($array, $k)
{
                for($i=0; $i<$k; $i++) {
                                $temp = $array[$i];
                                unset($array[$i]);
                                $array[] = $temp;
                }
                return $array;
}

The function works and the complexity is O(n), so it meets the requirement.

But there is a flaw with the rightShift function and that is always easy for people to neglect. We don't carefully consider the value of $k. If $k <= 0, that is fine, the array keeps same. But what if $k > count($array)? We tend to assume $k < count($array) so in the function we don't do anything about it. Actually, $k could be much bigger than count($array). The function still works when $k > count($array), but obviously, it is not efficient.

So let's consider when $k > count($array). In this example, if $k = 8, what the result should be? It should be array('d', 'e', 'a', 'b', 'c'). We can find that we don't really need to shift $k times, we only need to shift $k % count($array) times. So, let's change our code:

function rightShift($array, $k)
{
                $k = $k % count($array);
                for($i=0; $i<$k; $i++) {
                                $temp = $array[$i];
                                unset($array[$i]);
                                $array[] = $temp;
                }
                return $array;
}

This will actually introduce another issue: what if count($array) === 0? So, we need to check this:

function rightShift($array, $k)
{
                $total = count($array);
                if ($total === 0) {
                                return false;
      }
                $k = $k % $total;
                for($i=0; $i<$k; $i++) {
                                $temp = $array[$i];
                                unset($array[$i]);
                                $array[] = $temp;
                }
                return $array;
}

2 comments:

Anonymous said...

superb man, thank you.

Vale Co Xenia said...

Great & Useful Blog. Helped me a lot.
PHP Training in Chennai
PHP Online Training India