Solve unsorted-substring a second time

This solution operates in O(n) time instead of O(n*log(n)) time, which
surprisingly isn't *that* big of a difference...

Consider a size of n of 10M...
  1) ~10s
  2) ~0.5s

So, yes, the O(n*log(n)) will take 100x longer to complete, but for an enormous
input size of 10M elements, it can still complete in under a minute. The
difference between that and the second, faster, algorithm, is just 9s.

1 files changed, 51 insertions, 5 deletions

diff --git a/scratch/facebook/moderate/unsorted-substring.py b/scratch/facebook/moderate/unsorted-substring.py
index bc2229030fbd..de7326b05822 100644
--- a/scratch/facebook/moderate/unsorted-substring.py
+++ b/scratch/facebook/moderate/unsorted-substring.py
@@ -2,6 +2,10 @@
 # the starting and ending integers that, if their elements were sorted, the
 # entire array would be sorted.
 
+################################################################################
+# First Attempt
+################################################################################
+
 def unsorted_substring(xs):
     ys = xs[:]; ys.sort()
     m = 0
@@ -14,8 +18,50 @@ def unsorted_substring(xs):
         n -= 1
     return m, n
 
-print(unsorted_substring([1,2,4,7,10,11,7,12,6,7,16,18,19]))
-print(unsorted_substring([1,2,3,4]))
-print(unsorted_substring([4,3,2,1]))
-print(unsorted_substring([1,3,2,4]))
-print(unsorted_substring([2,1,3,4]))
+################################################################################
+# Second Attempt
+################################################################################
+
+def unsorted_substring_2(xs):
+    beg = 1
+    while xs[beg - 1] <= xs[beg]:
+        beg += 1
+        if beg >= len(xs):
+            return -1, -1
+    end = len(xs) - 2
+    while xs[end + 1] >= xs[end]:
+        end -= 1
+
+    min_mid = xs[beg]
+    max_mid = xs[beg]
+    i = beg + 1
+    while i <= end:
+        min_mid = min(min_mid, xs[i])
+        max_mid = max(max_mid, xs[i])
+        i += 1
+
+    # beg -= 1 until max(lhs) <= min(mid)
+    while beg - 1 >= 0 and xs[beg - 1] >= min_mid:
+        beg -= 1
+
+    # end += 1 while max(mid) <= min(rhs)
+    while end + 1 < len(xs) and max_mid >= xs[end + 1]:
+        end += 1
+    return beg, end
+
+################################################################################
+# Tests
+################################################################################
+
+xs = [
+    [1,2,4,7,10,11,7,12,6,7,16,18,19],
+    [1,2,3,4],
+    [4,3,2,1],
+    [1,3,2,4],
+    [2,1,3,4],
+]
+
+for x in xs:
+    print("Testing: {}".format(x))
+    print("1) {}".format(unsorted_substring(x)))
+    print("2) {}".format(unsorted_substring_2(x)))