about summary refs log tree commit diff
path: root/scratch/facebook/moderate/unsorted-substring.py
diff options
context:
space:
mode:
authorWilliam Carroll <wpcarro@gmail.com>2020-11-14T15·07+0000
committerWilliam Carroll <wpcarro@gmail.com>2020-11-14T15·08+0000
commit48fde5f27838b63d33fe69eb5f13f5d54314555d (patch)
tree959c3fef0487ee4045a26157c49284673a7efb48 /scratch/facebook/moderate/unsorted-substring.py
parent47c5c6ac05e7c42d7586d7248a2ec175b91b620e (diff)
Solve unsorted-substring
Write a function that returns the indices demarcating a substring, which if
sorted, would make the entire array sorted.
Diffstat (limited to 'scratch/facebook/moderate/unsorted-substring.py')
-rw-r--r--scratch/facebook/moderate/unsorted-substring.py21
1 files changed, 21 insertions, 0 deletions
diff --git a/scratch/facebook/moderate/unsorted-substring.py b/scratch/facebook/moderate/unsorted-substring.py
new file mode 100644
index 000000000000..bc2229030fbd
--- /dev/null
+++ b/scratch/facebook/moderate/unsorted-substring.py
@@ -0,0 +1,21 @@
+# Write a function that accepts an array of integers and returns the indices for
+# the starting and ending integers that, if their elements were sorted, the
+# entire array would be sorted.
+
+def unsorted_substring(xs):
+    ys = xs[:]; ys.sort()
+    m = 0
+    while xs[m] == ys[m]:
+        m += 1
+        if m >= len(xs):
+            return -1, -1
+    n = len(xs) - 1
+    while xs[n] == ys[n]:
+        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]))