Additional solution for challenge 289 task 1, by Tim King

2 files changed, 70 insertions, 2 deletions

diff --git a/challenge-289/jtimothyking/csharp/ch-1.cs b/challenge-289/jtimothyking/csharp/ch-1.cs
index 24e79631a2..8ecd2e058c 100644
--- a/challenge-289/jtimothyking/csharp/ch-1.cs
+++ b/challenge-289/jtimothyking/csharp/ch-1.cs
@@ -4,6 +4,12 @@ public static class Ch1
 {
     public static void Main(string[] args)
     {
+        // Call whichever implementation you'd like to use.
+        PrintThirdMax_impl2(args);
+    }
+
+    private static void PrintThirdMax_impl1(string[] args)
+    {
         var firstThree = args.Select(int.Parse)
             .OrderDescending().Distinct()
             .Take(3).ToArray();
@@ -14,6 +20,16 @@ public static class Ch1
         );
     }
 
+    private static void PrintThirdMax_impl2(string[] args)
+    {
+        var firstThree = args.Select(int.Parse).Max3().ToArray();
+        Console.WriteLine(
+            firstThree.Length >= 3 ? firstThree[2] :
+            firstThree.Length > 0 ? firstThree[0] :
+            ""
+        );
+    }
+
     private static IEnumerable<T> Distinct<T>(this IOrderedEnumerable<T> source)
     {
         using var enumerator = source.GetEnumerator();
@@ -29,4 +45,26 @@ public static class Ch1
             yield return current;
         }
     }
+
+    /// <summary>Return the top 3 unique maximum integers in O(n) time.</summary>
+    private static IEnumerable<T> Max3<T>(this IEnumerable<T> source)
+    {
+        const int numMaxValues = 3;
+        var comparer = Comparer<T>.Default;
+        var maxValues = new List<T>();
+        foreach (var value in source) InsertIfNewMax(value);
+        return maxValues;
+
+        void InsertIfNewMax(T value)
+        {
+            for (var i = 0; i < numMaxValues; i++)
+            {
+                if (i < maxValues.Count && comparer.Compare(value, maxValues[i]) == 0) break;
+                if (i < maxValues.Count && comparer.Compare(value, maxValues[i]) <= 0) continue;
+                maxValues.Insert(i, value);
+                if (maxValues.Count > numMaxValues) maxValues.RemoveAt(numMaxValues);
+                break;
+            }
+        }
+    }
 }
\ No newline at end of file
diff --git a/challenge-289/jtimothyking/perl/ch-1.pl b/challenge-289/jtimothyking/perl/ch-1.pl
index 1ea9bf70f7..9c808466fc 100644
--- a/challenge-289/jtimothyking/perl/ch-1.pl
+++ b/challenge-289/jtimothyking/perl/ch-1.pl
@@ -4,7 +4,37 @@ use warnings;
 
 use List::Util qw(uniqint);
 
-my @unique_ints = uniqint sort { $b <=> $a } @ARGV;
-say $unique_ints[2] // $unique_ints[0];
+# Call whichever implementation you'd like to use.
+implementation_2();
+
+sub implementation_1 {
+    my @unique_ints = uniqint sort { $b <=> $a } @ARGV;
+    say $unique_ints[2] // $unique_ints[0];
+}
+
+sub implementation_2 {
+    my @max_ints = max3(@ARGV);
+    say $max_ints[2] // $max_ints[0];
+}
+
+# Return the top 3 unique maximum integers in O(n) time.
+sub max3 {
+    my $num_max_ints = 3;
+    my @max_ints;
+
+    my sub insert_if_new_max {
+        my $int = shift;
+        for my $i (0 .. $num_max_ints - 1) {
+            last if $int == $max_ints[$i];
+            next if (defined $max_ints[$i] && $int < $max_ints[$i]);
+            splice @max_ints, $i, 0, $int;
+            pop @max_ints if @max_ints > $num_max_ints;
+            last;
+        }
+    }
+
+    insert_if_new_max($_) for (@_);
+    return @max_ints;
+}
 
 __END__