# Sorting with a deque

You're given an array of positive integers. Your job is to sort them using an initially empty deque (double-ended queue) by the following procedure:

• Take a number from the front of the array, and push it into one of the two ends of the deque. Repeat this until the array is empty.

Determine if it is possible that the deque is sorted from left to right in the end.

You may assume that the array is not empty. The input numbers are not necessarily distinct.

For output, you can choose to

• output truthy/falsy using your language's convention (swapping is allowed), or
• use two distinct, fixed values to represent true (affirmative) or false (negative) respectively.

Standard rules apply. The shortest code in bytes wins.

## Test cases

Truthy:

[1]
[1, 2, 3, 4]
[4, 3, 2, 1]
[10, 10, 10, 10]
[3, 4, 2, 5, 1, 6]
[4, 3, 5, 2, 6, 1]
[5, 4, 4, 5, 3, 5, 3, 6, 2, 6]


Falsy:

[1, 3, 2]
[3, 1, 2]
[4, 3, 2, 3, 2, 1]
[1, 2, 3, 2, 3, 4]
[4, 5, 4, 3, 4, 5]

• Related Commented Jul 15 at 1:14
• Related: Antsy Permutations, which I think is this restricted to permutations
– xnor
Commented Jul 15 at 20:48

# K (ngn/k), 17 bytes

{&/(x=|\x)|x=&\x}


Every element must be the minimal (or the maximal) element of its prefix.

Try it online!

# APL(Dyalog Unicode), 13 10 bytes SBCS

A direct translation of the ngn/k solution. -3 bytes thanks to @att.

⊢∧.∊⌈⍀,¨⌊⍀


Try it on APLgolf! (10 bytes)

(⊢=⌈⍀)∧.∨⊢=⌊⍀


Try it on APLgolf! (13 bytes)

# Uiua, 14 13 bytes

Probably can be improved as I'm not so familiar with Uiua.

/↧↥=⟜\↧:=⟜\↥.


Try it on Uiua pad! (13 bytes)

/↧↥⊃(=⟜\↧)=⟜\↥


Try it on Uiua pad! (14 bytes)

• apl -3: ⊢∧.∊⌈⍀,¨⌊⍀
– att
Commented Jul 15 at 18:01
• uiua -1: /↧↥∩=⊃⟜\↧⟜\↥, and -2 with a slightly different approach: /↧↥∩=∩⟜\↥¯.
– ovs
Commented Jul 18 at 15:41

# Python, 45 bytes

f=lambda l:min(l)<l.pop()<max(l)or l and f(l)


Attempt This Online!

Returns flipped truth values: Falsey (empty list) for sortable and True for not sortable. Consumes the input list.

# Jelly,  7  6 bytes

ṢƤtƑ"ḋ


A monadic Link that accepts a list of positive integers and yields 0 (falsey) if sortable or a positive integer (truthy) if not.

Try it online!

#### How?

Check that each sorted prefix has its original rightmost element at one end.

ṢƤtƑ"ḋ - Link: list of positive integers, A
Ƥ     - for each prefix:
Ṣ      -   sort
"  - zip with E in A applying f(SortedPrefix, E):
Ƒ   -   is invariant under?:
t    -     trim any {E} from both sides of {SortedPrefix}
ḋ - dot-product with {A}


# R, 30 bytes

$$x,!=cummin)any(x-!x&x+!-x)  Attempt This Online! Outputs swapped TRUE/FALSE. Slightly ungolfed: \(x)any(x-cummin(x)&(-x)-cummin(-x))  # Vyxal, 9 bytes ɖ∵?ɖ∴ZΠḟ  Try it Online! Port of Unrelated String's Jelly answer, and a bit of a mess. I tried writing my own answer, but it was a byte longer.  ḟ # Is every element of the input ZΠ # Either ɖ∵ # A cumulative minimum ɖ∴ # Or a cumulative maximum ? # Of the input?  # Nekomata + -e, 6 bytes pƆᵗ≤ᵗ≥  Attempt This Online! This swaps truthy and falsy. pƆᵗ≤ᵗ≥ p Find a prefix of the input Ɔ Split it into the last element and the rest ᵗ≤ Check that the last is less than at least one element of the rest ᵗ≥ Check that the last is greater than at least one element of the rest  # Jelly, 8 bytes «\ż»\Œpi  Try it online! Feels a bit silly, but beats a couple better ideas I've had.  Œp Generate every list built by choosing from, at each position, ż either «\ the cumulative minima »\ or the cumulative maxima. i Is the input in this list?  # Jelly, 8 bytes n«\×»\o⁼  Try it online! n Is each element not equal to «\ the smallest element so far? × Multiply those comparisons pairwise with »\ the cumulative maxima, o then replace zeroes with corresponding elements of the input. ⁼ Is this result equal to the input?  # Haskell + hgl, 23 bytes no uq<f'[gj,mx,mn]<<pxn  Attempt This Online! ## Explanation For each prefix determine the maximum, minimum and last elements. If any of these results in 3 unique values then fail otherwise pass. • pxn all non-empty prefixes • f' apply all functions in a list ... • gj last • mx maximum • mn minimum • no none is ... • uq unique If the result is unique it means that there is an element which has both a greater and smaller element before it, and thus that element cannot be inserted into the deque. # Alternative algorithm, 34 bytes f x=fo(zW ma.*eq=#=x.*flz x)mN ma  Attempt This Online! ## Explanation We check that every element of the input is either a cumulative minimum or a cumulative maximum. • Take the cumulative minimum and maximum of the input. • Zip each with the original list to determine the equal elements. • Zip the two results together with or. • Check that every element in the result is true. # Reflection This seems pretty poor overall. The second submission is very long but can be improved in a lot of ways. I don't see any sensible way to shorten the first submission. Part of why the alterntive is so much longer is it seems to be that the algorithm uses a lot of references to the input. (The most expanded version references the input 4 times!) This makes the glue pretty costly. • lz ma and lz mN for cumulative maximum and minimum could have pre-composed variants. • zW ma, zW mN, and zW eq could all also have shortcuts. Generally zW could have more shortcuts. • I implemented jzW to zip and concat lists. I chose to generalize this to any monad, however we can see in the above that it would have been useful to have generalized to a monoid. I'll leave the existing version, but I should make a version which zips and then uses a monoid action to combine the values. # K (ngn/k), 13 bytes &/|/=/&\'\-:\  Try it online! Returns a positive integer for truthy and 0 for falsy. I don't think I've seen any other code with such high slash ratio :) &/|/=/&\'\-:\ Input: x = a vector of positive integers -:\ negate and collect until convergence; gives [x, -x] since x is nonempty and positive &\'\ "minimum scan each" until convergence; if x is all-equal, becomes [[x, -x]]; otherwise [[x, -x], [cummin of x, cummin of -x]] note that cummin of -x is -(cummax of x) =/ reduce by elementwise equality; [x, -x] or [x == cummin of x, x == cummax of x] |/ reduce by max; x or (x[i] == (cummin of x)[i] or (cummax of x)[i] for each i) &/ reduce by min  # 05AB1E, 11 10 bytes ηε{DyθÚÊ}P  -1 byte porting @JonathanAllan's Jelly answer Outputs 1 if sortable; 0 if not. Original approach: δ.SÅlεÙg}3å  Outputs 0 if sortable; 1 if not. Explanation: η # Get all prefixes of the (implicit) input-list ε # Map over each prefix y: { # Sort it D # Duplicate this sorted prefix y # Push the current prefix y again θ # Pop and keep its last item Ú # Trim all leading/trailing occurrences of this value from the # sorted copy Ê # Check that the two lists are NOT the same }P # After the map: product to check all were truthy # (after which this is output implicitly as result)  δ # Apply double-vectorized on two times the (implicit) input-list: .S # Compare (-1 if a<b; 0 if a==b; 1 if a>b) Ål # Pop and leave just the lower triangle of this matrix ε # Map over each row of the lower triangle: Ù # Uniquify g # Pop and push the length }3å # After the map: check whether there is a 3 in the list # (after which this is output implicitly as result)  # Nibbles, 13 nibbles (6.5 bytes) ?*!$[\@]:  Attempt This Online! ?*!$[\@]: # full program ?*!$[\@]: # with implicit variable shown ? # index of the input array in * # cartesian product of: ! : # zip together by concatenating elements: $[ # scan over input by minimum # (=cumulative minumum) \@] # scan over input by maximum # (=cumulative maximum)  • I'm always blown away by how simultaneously expressive and compact this language is, it's really something awesome. :D Commented Jul 16 at 1:40 • @ConorO'Brien ...and it's relatively easy to learn, once one gets one's head around the concept of DeBruijn-indexed variables. There certainly aren't a huge number of built-ins to rememnber. Give it a shot! It'd be great to have some more Nibbles competition! Commented Jul 16 at 8:39 # JavaScript (ES6), 39 bytes Returns a Boolean value. a=>a.every(m=v=>(v>a?v:a=v)<m?a==v:m=v)  Try it online! ### Commented a => // a[] = input array, re-used as the lower bound a.every(m = // m = upper bound, initially NaN'ish v => // for each value v in a[]: ( v > a ? // if v is greater than the lower bound: v // use v directly : // else: a = v // update the lower bound to v ) < m ? // if v is lower than the upper bound: a == v // success if the lower bound is equal to v // failure otherwise (v is between the 2 bounds) : // else: m = v // update the upper bound to v (truthy) ) // end of every()  # Charcoal, 16 bytes ⬤θ№⟦⌊…θ⊕κ⌈…θ⊕κ⟧ι  Try it online! Link is to verbose version of code. Outputs a Charcoal boolean, i.e. - if the deque can be sorted, nothing if not. Explanation: Port of JonathanAllan's Jelly answer.  θ Input array ⬤ All elements satisfy θ Input array … Truncated to length κ Current index ⊕ Incremented ⌊ Minimum so far θ Input array … Truncated to length κ Current index ⊕ Incremented ⌈ Maximum so far ⟦ ⟧ Make into list № Contains ι Current element Implicitly print  # JavaScript (Node.js), 41 bytes x=>!x.some(p=q=t=>t<x[0]?p<(p=t):q>(q=t))  Try it online! Optimized # JavaScript (Node.js), 64 bytes f=([c,...x],...a)=>c?f(x,c,...a)|f(x,...a,c):!a.some(p=>c>(c=p))  Try it online! Raw parse of question # Go, 119 bytes import."slices" func f(l[]int)bool{for i:=1;i<len(l);i++{if p,e:=l[:i],l[i];e>Min(p)&&e<Max(p){return 0>1}} return 0<1}  Attempt This Online! Uses the fact (pointed out by @akamayu) that each element must be either the minimum or the maximum of it and all elements before it. # J, 16 14 bytes */@:+&(=>./$$-


Try it online!

-2 thanks to Bubbler!

Based on akamayu's idea, but applies max-scan to both the input and its negation instead of applying max and min scans, which saves bytes in J vs APL.

• -1: */@:+.&(=>./\)- or */ .+.&(=>./\)- Commented Jul 26 at 3:53
• Also I think it's OK to use + instead of +. since any nonzero is truthy. Commented Jul 26 at 4:02
• Thanks! I thought the +. over + was more of a codegolf site convention (meaning truthy/falsy return values need to be 1 of 2 distinct values), but since it's your question I'm happy to take advantage of that flexibility. Commented Jul 26 at 5:05