Decreasing-Increasing Array
May 29, 2020
The student’s suggestion to use binary search that takes O(log n) time doesn’t work because every element of the array must be examined to determine if the array is in decreasing-increasing order. Here is our solution:
(define (sorted? pred? xs)
(cond ((or (null? xs) (null? (cdr xs))) #t)
((not (pred? (car xs) (cadr xs))) #f)
(else (sorted? pred? (cdr xs)))))
(define (decr-incr xs)
(if (< (length xs) 3) #f
(let ((pivot (apply min xs)))
(let-values (((decr incr)
(split-while (lambda (x) (not (= x pivot))) xs)))
(if (and (not (null? decr)) (not (null? incr))
(sorted? >= decr) (sorted? <= incr))
pivot
#f)))))
That’s O(n) even though it makes four passes through the input (in length, min and split-whileand the two pieces of sorted?). Here are the example problems:
> (decr-incr '(10 10 10 8 8 6 4 4 3 12 13 22 31 40 59 68)) 3 > (decr-incr '(1 2 4 8 16 32 64)) #f
You can run the program at https://ideone.com/qTh5S7.
Programming Praxis 
It is hard to see how this can be done in O(logn), as all elements will have to be inspected. For example: 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 is decreasing-increasing. But change the 7th from 4 to 6 and it is not decreasing-increasing any more.
Pretty straight-forward problem. Here is my take on it in Julia 1.4.1: https://pastebin.com/XpBgPV6J
The code could use improvements so I’ll look into it further. However, as a first draft it should be acceptable (works well in relatively small arrays). Cheers!
As you say, a log(n) solution doesn’t seem possible, but a single pass and O(1) storage should be enough.
Here is a solution in R7RS Scheme that uses only a single pass and
detects an invalid input as early as possible without examining the
rest of the input. So it has excellent expected running time on
random inputs. :-) O(log n) is impossible for worst-case running time
because a valid sequence can be turned into an invalid one by changing
any element that the algorithm does not inspect.
(import (scheme base) (scheme write)) (cond-expand ((library (org eip10 okmij myenv)) (import (only (org eip10 okmij myenv) assert))) (else (define (assert . args) (for-each display args) (newline)))) (define samples ; ((input . output) ...) '(((10 10 10 8 8 6 4 4 3 12 13 22 31 40 59 68) . 3) ((1 2 4 8 12 32 64) . #f) (() . #f) ((1) . #f) ((1 2) . #f) ((2 1) . #f) ((2 1 3) . 1) ((7 3 2 4) . 2))) ;; If nums = (x xs ... y z zs ...) where (x xs ... y) is a ;; non-increasing sequence with y strictly smaller than at least one ;; other element and, similarly, where (y z zs ...) is a ;; non-decreasing sequence with y strictly smaller than at least one ;; element, then return y; else #f. (define (decreasing-increasing-pivot nums) (and (pair? nums) (let loop ((sfx (cdr nums)) ; suffix of nums, shortening by 1 at each step (prev (car nums)) ; element of nums just before sfx (dec? #f) (pvt #f)) ;; if pvt is true it is y and sfx = (zs ...) for above form ;; of nums, where the zs may not have the required form ;; (remains to be checked); else the prefix of nums (before ;; sfx) is non-increasing. dec? is true iff the prefix had at ;; least one strictly decreasing step. (if (null? sfx) pvt (cond ((< (car sfx) prev) (if pvt #f ; (y z zs ...) not non-decreasing as required (loop (cdr sfx) (car sfx) #t pvt))) ((> (car sfx) prev) (if (not pvt) (if (not dec?) #f ; (x xs ...) not non-increasing as required (loop (cdr sfx) (car sfx) #t prev)) ; found pivot (loop (cdr sfx) (car sfx) dec? pvt))) (else (assert (= (car sfx) prev)) (loop (cdr sfx) (car sfx) dec? pvt))))))) (assert (let ((r (map decreasing-increasing-pivot (map car samples)))) (equal? r (map cdr samples))))@programmingpraxis, for your solution,
(decr-incr '(1 2 4 8 16 32 64))returns#f, but(decr-incr '(64 32 16 8 4 2 1), returns 1. If the lack of a decreasing prefix does not succeed, my expectation is that the lack of an increasing suffix would also not succeed.Here’s a solution in C.
#include <stdbool.h> #include <stdio.h> #include <stdlib.h> bool dec_inc_array(int* array, int n, int* pivot) { int i = 0; while (i + 1 < n && array[i] >= array[i + 1]) ++i; if (i == 0 || i == n - 1) return false; *pivot = array[i]; while (i + 1 < n && array[i] <= array[i + 1]) ++i; return i == n - 1; } int main(int argc, char* argv[]) { int n = argc - 1; int* array = malloc(sizeof(int) * n); for (int i = 0; i < n; ++i) { array[i] = atoi(argv[i + 1]); } int pivot; bool success = dec_inc_array(array, n, &pivot); if (success) printf("%d\n", pivot); free(array); return success ? EXIT_SUCCESS : EXIT_FAILURE; }Example usage:
There’s a bug in my earlier solution. Calling the code with
3 3 5returns3, whereas I think this should return no solution. An update to line 9 addresses this issue.#include <stdbool.h> #include <stdio.h> #include <stdlib.h> bool dec_inc_array(int* array, int n, int* pivot) { int i = 0; while (i + 1 < n && array[i] >= array[i + 1]) ++i; if (i == 0 || i == n - 1 || array[i] == array[0]) return false; *pivot = array[i]; while (i + 1 < n && array[i] <= array[i + 1]) ++i; return i == n - 1; } int main(int argc, char* argv[]) { int n = argc - 1; int* array = malloc(sizeof(int) * n); for (int i = 0; i < n; ++i) { array[i] = atoi(argv[i + 1]); } int pivot; bool success = dec_inc_array(array, n, &pivot); if (success) printf("%d\n", pivot); free(array); return success ? EXIT_SUCCESS : EXIT_FAILURE; }In Python using 3 states. INIT means no decrease happend yet. DECREASED means there was a decrease and INCREASE means there was an increase (after a decrease). The logic is simple. If the value does not change, there is nothing to do. The minimum value can be set if the state goes from DECREASED to INCREASED.
INIT, DECREASED, INCREASED = 0, 1, 2 def is_decr_incr(seq): state, minimum = INIT, False for a, b in zip(seq, seq[1:]): if a > b: # decreasing if state == INIT: state = DECREASED elif state == INCREASED: return False elif a < b: # increasing if state == INIT: return False if state == DECREASED: state, minimum = INCREASED, a return minimumHere’s a Haskell version.
import Data.Bool (bool) -- The minimum element of a decreasing-increasing sequence, or nothing if the -- argument is not such a sequence. (We require that the sequence have a -- minimum that is strictly smaller than the first and last elements.) decinc :: Ord a => [a] -> Maybe a decinc xs = case span (uncurry (>=)) $ zip xs (drop 1 xs) of ((d, _):_, (i, _):_) -> bool Nothing (Just i) (d > i) _ -> Nothing test :: (Ord a, Show a) => [a] -> IO () test xs = putStrLn $ show (decinc xs) ++ ": " ++ show xs main :: IO () main = do test [10, 10, 10, 8, 8, 6, 4, 4, 3, 12, 13, 22, 31, 40, 59, 68] test [1, 2, 4, 8, 12, 32, 64] test ([] :: [Int]) test [5] test [5, 5] test [5, 6] test [5, 5, 6] test [5, 6, 6]A solution in Racket.
As observed before, we cannot determine whether or not the array given is in Decreasing-Increasing order without examining all of the array elements. Doing so, forces a O(n) solution. I think that the wording was off however, and that we should assume that the array is in Decreasing-Increasing order, then throw an error iff we detect a contradiction while searching for the pivot. Assuming that the array is ordered, makes this a more interesting problem. However, in the worst case, every element is the same. Any algorithm that tried to find the pivot in such an array would still be required to examine all of the elements. Accordingly, the worst case performance is still O(n). But we can do better than this on average:
pivot :: [Int] -> Int pivot [x] = x pivot xs@(_:_) = let i = div (length xs - 1) 2 j = i + 1 in pivot $ if xs !! i < xs !! j then take j xs else if xs !! i > xs !! j then drop (i + 1) xs else take (i + 1) xs ++ drop (j + 1) xsThis leads to traces such as the following:
Which exhibit O(log(n)) behavior. I suspect that this is what the instructor meant.