about summary refs log tree commit diff
path: root/scratch/facebook/moderate/unsorted-substring.py
blob: de7326b05822d56f2f14dad602d335c516c352e5 (plain) (blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
# 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.

################################################################################
# First Attempt
################################################################################

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

################################################################################
# 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)))