DEV Community

Bob Lied
Bob Lied

Posted on

PWC 263.1 Don't Sort It, Be Happy

PWC 263, Task 1 Target Index

Here's a little blog I wrote. You might want to read it note for note.

You are given an array of integers, @ints, 
and a target element $k.

Write a script to return the list of indices
in the sorted array where the element is the
same as the given target element.
Enter fullscreen mode Exit fullscreen mode

Example 1

  • Input: @ints = (1, 5, 3, 2, 4, 2), $k = 2
  • Output: (1, 2)
    • Sorted array: (1, 2, 2, 3, 4, 5)
    • Target indices: (1, 2) as $ints[1] = 2 and $ints[2] = 2

Dive right in

Well, the example gives it away, doesn't it? Sort the array and waddle up the list to the first index where $k exists. Then, because the array is sorted, all the other places where $k exists must be adjacent.

Or not

But hold on. In every algorithm we have some trouble, but when you sort you make it double.

All the $k together means we've effectively partitioned the array into three sets: elements that are less than $k, elements equal to $k, and the rest.

We don't have to sort the array at all. We just have to traverse the array and count the elements in the first two partitions.

sub targetIndex($k, @ints)
{
    my ($below, $same) = (0, 0);
    foreach ( @ints )
    {
        if    ( $_ < $k )  { $below++ }
        elsif ( $_ == $k ) { $same++ }
    }
    return [] if $same == 0;
    return [ $below .. ($same + $below - 1) ];
}
Enter fullscreen mode Exit fullscreen mode

If $k doesn't appear at all, we can bail out by returning an empty list. $below and $same tell us the range of numbers we need in the answer.

$below = 1 # 1 element less than $k
$same  = 2 # 2 elements equal to $k
      {         } 
   1  {  2   2  }   3   4   5
  [0] { [1] [2] }  [3] [4] [5]
         ^   ^
         |   +---- $below + $same -1 = 1+2-1 = 2
  $below-+
Enter fullscreen mode Exit fullscreen mode

The .. range operator makes short work of creating the sequence of numbers we want.

Put that range of numbers into an array, and we have our answer. This function is returning array references, not arrays, so the calling function will have to de-reference. In context, it might look like

say "(", join(",", targetIndex($Target, @ARGV)->@*), ")";
Enter fullscreen mode Exit fullscreen mode

Now there is the blog I wrote. I hope you liked the way I code. Don't worry, be hacker.

Top comments (3)

Collapse
 
barbevivien profile image
Barbe Vivien

Hi Bob, thanks for your inspiring article. An interesting approach. However, there's a sentence that keeps playing in my mind when analyzing your text: don't make me think (the motto I learned from my students). IMHO, sorting the array and checking if $k has a match, providing the requested indices, is more straightforward than your approach, at least for me. Gives your solution better a performance? Are there other advantages? Anyway, thanks again! Best regards, Reinier

Collapse
 
boblied profile image
Bob Lied

Sorting is probably O(n log n), compared to one pass over the array O(n), so it will give better performance, if the arrays were bigger or the function was called enough times. Also, sorting the array will make a copy of the array, so it takes more space to sort.

Collapse
 
muthm profile image
Matthias Muth

Great idea, and great explanation!
Thanks for the inspiration!