Piling Up with Python This is my solution for a Hackerrank problem. The problem was:


  There is a horizontal row of cubes. The length of each cube is given. You need to create a new vertical pile of cubes. The new pile should follow these directions: if cube_i is on top of cube_j then sideLength_j &gt;= sideLength_i. 
  
  When stacking the cubes, you can only pick up either the leftmost or the rightmost cube each time. Print "Yes" if it is possible to stack the cubes. Otherwise, print "No". Do not print the quotation marks.
  
  Input Format
  
  The first line contains a single integer T, the number of test cases.
  For each test case, there are 2 lines.
  The first line of each test case contains , the number of cubes.
  The second line contains space separated integers, denoting the sideLengths of each cube in that order.
  
  Constraints

1 &lt;= T &lt;= 5
1 &lt;= n &lt;= 10**5
1 &lt;= sideLength &lt;= 2**31

  
  Output Format
  
  For each test case, output a single line containing either "Yes" or "No" without the quotes.
  
  Sample Input

2
6
4 3 2 1 3 4
3
1 3 2

  
  Sample Output

Yes
No

  
  Explanation
  
  In the first test case, pick in this order: left - 4, right - 4, left - 3, right - 3, left - 2, right - 1.
  In the second test case, no order gives an appropriate arrangement of vertical cubes. 3 will always come after either 1 or 2.


My code is actually rather short:

if __name__ == '__main__':
    num_tests = int(input().strip())

    for _ in range(num_tests):
        num_cubes = int(input().strip())
        cube_sidelengths = list(map(int, map(str.strip, input().strip().split())))


        i, j = 0, len(cube_sidelengths)-1
        pile = []

        while i != j:
            left, right = cube_sidelengths[i], cube_sidelengths[j]
            # In case there is nothing in the pile just add the bigger one
            if not pile:
                if left &gt; right:
                    pile.append(left)
                    i += 1
                else:
                    pile.append(right)
                    j -= 1
            else:
                # Take the bigger of the left and right element and compare it
                # to the last item on the pile. If it's bigger we can't pile
                # it up, otherwise put it on the pile and continue
                if left &gt; right:
                    if left &gt; pile[-1]:
                        print('No')
                        break
                    else:
                        pile.append(left)
                        i += 1
                else:
                    if right &gt; pile[-1]:
                        print('No')
                        break
                    else:
                        pile.append(right)
                        j -= 1
        else:
            print('Yes')


But I'm actually not very satisfied with the code. It passes all Hackerrank tests but I can't help feeling that it's missing something - but I can't put my finger on it.

An additional thing that has been bugging me was that it was part of the  "Python collections" problems but I haven't used anything from the collections module. It would be possible to use a deque here but that felt like overkill - because pop and popLeft are O(1) but just keeping the indices and accessing a list is also O(1) so it wouldn't even provide better asymptotic behaviour. So as additional question: Is there anything that could be improved by using a deque?

Otherwise I would be very glad about any feedback how I could improve the code.
The algorithm is actually pretty efficient, so congrats for that.

The first thing that I'd like to suggest is moving the logic outside the main check. In python, it's fairly common (and IMO more readable) to have your structure like this:

imports

def pile_algo(*args, **kwargs):
    """Docstring here"""
    # your code


def main():
    """Docstring here"""
    # process pile_algo

if __name__ == '__main__':
    main()


Of course, the main() is optional if you already have all the logic inside pile_algo().

Even if I said the algorithm is good, we can improve the way you're doing things.

You're not using num_cubes variable, so you can remove it (int(input().strip()) it's enough). Moving forward, neither use of strip() or list() or map() is necessary in your:

cube_sidelengths = list(map(int, map(str.strip, input().strip().split())))


You can rewrite that as:

cube_sidelengths = [int(x) for x in input().split()]




Apart from that, I don't have any other reasons to think about using deque. If it works, it works. And apparently works better enough to get over it.

Though, of course, I would also ask: Is it too slow right now? Most of the times, the aim of a programming challenge is both getting familiar with a specific library/module and improve your algorithms skills. You said:


  It would be possible to use a deque here but that felt like overkill -
  because pop and popLeft are O(1) but just keeping the indices and
  accessing a list is also O(1) so it wouldn't even provide better
  asymptotic behavior.


Well, it would provide a worse asymptotic behavior? Just start writing a deque-based solution and see what improvements might that bring. I can think of a few right now:


the code will be more comprehensive because of deque's already builtin methods which might do what you manually did (pop, etc..)
talking about efficiency, Python lists are much better for random-access and fixed-length operations, including slicing, while deques are much more useful for pushing and popping things off the ends, with indexing (but not slicing, interestingly) being possible but slower than with lists.


From the docs:


  Deques support thread-safe, memory efficient appends and pops from
  either side of the deque with approximately the same O(1) performance
  in either direction.
  
  Though list objects support similar operations, they are optimized for
  fast fixed-length operations and incur O(n) memory movement costs for
  pop(0) and insert(0, v) operations which change both the size and
  position of the underlying data representation.




This might look more of a theory answer, and might not specifically answer your question, but I just wanted to highlight a couple of things out.