Continuing the Leetcode streak with more Python solving. I have a New Year's Resolution related to Leetcode but I feel that to speak it is to jynx it.

Before solving/typing these up (I do it at the same time) I completed 595. It required a short SQL query checking two conditions. The speed-up catch was using a UNION.

- Sort Array By Parity

Problem: Given a list `N`

return an array split by even/odd from the numbers in `N`

.

I'm using more high performance collections from Python today. Get ready for a speedy double ended queue.

from collections import dequeclass Solution:def sortArrayByParity(self, A):""":type A: List[int]:rtype: List[int]"""even_odd = deque()for num in A:if num % 2 == 0:even_odd.appendleft(num)else:even_odd.append(num)return list(even_odd)

Deques are a generalization of stacks and queues (the name is pronounced “deck” and is short for “double-ended queue”). 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.

The runtime complexity for this solution is `O(n)`

due to the above statement and the fact that we have iterated through `N`

just once. The space complexity is `O(n)`

.

I wonder if there's a faster version where the deque isn't converted to a list..

- Robot Return to Origin

Problem: Will this robot return home? Moving on a 2D plane via the commands: `U R D L`

.

Or, up, right, down, or left. This solution came to me instantly.

class Solution:def judgeCircle(self, moves):""":type moves: str:rtype: bool"""x = 0y = 0for i in moves:if i == 'U':y += 1if i == 'R':x += 1if i == 'D':y -= 1if i == 'L':x -= 1return x == 0 and y == 0

Runtime complexity: `O(n)`

Space complexity: `O(1)`

I did like this person's (4x slower) Python one-liner though:

`return moves.count('L') - moves.count('R') == moves.count('D') - moves.count('U') == 0`

- Self Dividing Numbers

Problem: Given a range of numbers `N`

-> `M`

return a list of self-divding numbers within that range.

Note: the range is inclusive, and a self-dividing num doesn't have a 0.

The example they give is `128 % 1 == 0`

, `128 % 2 == 0`

, `128 % 8 == 0`

hence 128 is self-dividing.

I used an enclosed function to break this one up a bit.

class Solution:def selfDividingNumbers(self, left, right):""":type left: int:type right: int:rtype: List[int]"""self_dividing = list()for i in range (left, right+1):def can_divide(num):digits = numwhile digits:digit = digits % 10if digit == 0 or num % digit != 0:return Falsedigits //= 10return Trueif can_divide(i):self_dividing.append(i)return self_dividing

Runtime: 68 ms, faster than 75.67% of Python3 online submissions for Self Dividing Numbers.

The trick here is getting the digits of the number without resorting to slow tricks like casting it to a string and slicing it.

Runtime complexity: Iterating through the range means `O(m - n)`

-- all other operations are `O(1)`

.

Space complexity: The range is the max list size we hold so `O(m - n)`

as well.