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.

Pages: 1 2

11 Responses to “Decreasing-Increasing Array”

  1. Paul said

    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.

  2. Zack said

    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!

  3. matthew said

    As you say, a log(n) solution doesn’t seem possible, but a single pass and O(1) storage should be enough.

  4. chaw said

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

  5. Daniel said

    @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.

  6. Daniel said

    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:

    $ ./a.out 10 10 10 8 8 6 4 4 3 12 13 22 31 40 59 68
    3
    $ ./a.out 1 2 4 8 16 32 64
    $ ./a.out 64 32 16 8 4 2 1
    $ ./a.out 3 2 -2 1 5
    -2
    $ ./a.out 3 2 -2 1 5 4
    
    
  7. Daniel said

    There’s a bug in my earlier solution. Calling the code with 3 3 5 returns 3, 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;
    }
    
  8. Paul said

    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 minimum
    
  9. Globules said

    Here’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]
    
    $ ./decinc
    Just 3: [10,10,10,8,8,6,4,4,3,12,13,22,31,40,59,68]
    Nothing: [1,2,4,8,12,32,64]
    Nothing: []
    Nothing: [5]
    Nothing: [5,5]
    Nothing: [5,6]
    Nothing: [5,5,6]
    Nothing: [5,6,6]
    
  10. r. clayton said

    A solution in Racket.

  11. Larry Lee said

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

    This leads to traces such as the following:

    *Main Data.List> pivot [3, 3, 3, 3, 3, 1, 3, 3]                                                                                                                                                                    
    [pivot] xs: [3,3,3,3,3,1,3,3]                                                                                                                                                                                      
    [pivot] xs: [3,3,3,3,1,3,3]                                                                                                                                                                                        
    [pivot] xs: [1,3,3]                                                                                                                                                                                                
    [pivot] xs: [1,3]                                                                                                                                                                                                  
    1                                                                                                                                                                                                                  
    *Main Data.List> pivot [13, 11, 11, 11, 5, 3, 3, 7, 11, 27]                                                                                                                                                        
    [pivot] xs: [13,11,11,11,5,3,3,7,11,27]                                                                                                                                                                            
    [pivot] xs: [3,3,7,11,27]                                                                                                                                                                                          
    [pivot] xs: [3,3,7]                                                                                                                                                                                                
    [pivot] xs: [3,3]                                                                                                                                                                                                  
    3                                                                                                                                                                                                                  
    *Main Data.List> pivot [8,8,8,5,4,2,4,6,6,9]                                                                                                                                                                       
    [pivot] xs: [8,8,8,5,4,2,4,6,6,9]                                                                                                                                                                                  
    [pivot] xs: [2,4,6,6,9]                                                                                                                                                                                            
    [pivot] xs: [2,4,6,9]                                                                                                                                                                                              
    [pivot] xs: [2,4]                                                                                                                                                                                                  
    2      
    

    Which exhibit O(log(n)) behavior. I suspect that this is what the instructor meant.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: