Valid Parentheses

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.

First of all, if this string has an odd number of characters, we know already that it isn't valid.

class Solution(object):
    def isValid(self, s):
        if len(s) % 2 == 1:
            return False

Go through each character, and if they are open characters(open parens, open bracket, open curlies), push it onto a stack.

        openparens = []
        for i in range(len(s)):
            if s[i] == '(' or s[i] == '[' or s[i] == '{':
                openparens.append(s[i])

Then, if it is any closing character, pop one off of the stack and make sure it is the opening character is the corresponding type. If everything goes well we will pass through the string nicely and return True.

            elif s[i] == ')':
                if len(openparens) == 0 or openparens.pop() != '(':
                    return False
            elif s[i] == ']':
                if len(openparens) == 0 or openparens.pop() != '[':
                    return False
            else:
                if len(openparens) == 0 or openparens.pop() != '{':
                    return False
        return True

Read More

Remove Nth Node from End of List

Given a linked list, remove the nth node from the end of list and return its head.

For example,
Given linked list: 1->2->3->4->5, and n = 2.
After removing the second node from the end, the linked list becomes 1->2->3->5.

Note:
Given n will always be valid.
Try to do this in one pass.

We are given the ListNode class

class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None

First, let's set two pointers to go through the linked list.

class Solution(object):
    def removeNthFromEnd(self, head, n):
        needle = head
        end = head

Then, we want to move the end pointer past the needle pointer by n steps. After that we move both pointers until end is the last node of the linked list.

        for i in range(n-1):
            end = end.next

        while end.next != None:
            needle = needle.next
            end = end.next

Notice that needle pointer will always be n steps behind the end pointer. Thus, when the end pointer is at the last node, the needle pointer is pointing at the (n+1)th last node. From there, we drop out the nth to last node by setting needle.next to the next next node.

        needle.next = needle.next.next
        return head

We can always change it return the value of the head through head.val. Now we can test it out using this:

numbers = ListNode(1)
numbers.next = ListNode(2)
numbers.next.next = ListNode(3)
numbers.next.next.next = ListNode(4)
n = 2
sol = Solution()
print sol.removeNthFromEnd(numbers, n)

This question is quite similar to this that I've done some time back. It's in a different language though(C).

Read More

ZigZag Conversion

The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this:

P   A    H   N
A P L S  I  I  G
Y       I      R
And then read line by line: "PAHNAPLSIIGYIR"
Write the code that will take a string and make this conversion given a number of rows:

string convert(string text, int nRows);
convert("PAYPALISHIRING", 3) should return "PAHNAPLSIIGYIR".

class Solution(object):
    def convert(self, s, numRows):
        """
        :type s: str
        :type numRows: int
        :rtype: str
        """
        rows = ["" for x in range(numRows)]
        count = 0
        start = 0
        end = numRows
        inc = 1

        # while we dont run out of letters
        while count < len(s):
            # count from index 0 -> numRows -> numRows
            for i in range(start, end, inc):
                if count < len(s):
                    rows[i] += s[count]
                    count += 1

            if inc == 1:
                inc = -1
                start = numRows-2
                end = 0
            else:
                inc = 1
                start = 0
                end = numRows
        return "".join(rows)


sol = Solution()
s = "PAYPALISHIRING"
numRows = 3
print sol.convert(s, numRows)

This solution goes through the string once, using a loop that changes direction when it hits the number of rows. Then, this simply joins the separated rows of strings into one, which makes an O(n) complexity.

Read More

Two Sum

Given an array of integers, return indices of the two numbers such that they add up to a specific target. You may assume that each input would have exactly one solution.

Example:
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        for i in range(len(nums)):
            for j in range(len(nums)):
                if i!=j:
                    if nums[i] + nums[j] == target:
                        return [i, j]


nums = [2, 7, 11, 15]
target = 9
sol = Solution()
print sol.twoSum(nums, target)

This is simple since you can look through each element in the array and compare their sum with the target number. But, the complexity of this solution is O(n^2), since you are going through the list once every element in the list.

What about this?

class Solution(object):
    def twoSum(self, nums, target):
        dict = {}
        for i in range(len(nums)):
            if dict.has_key(target-nums[i]):
                return (dict[target-nums[i]][1], i)
            else:
                dict.setdefault(nums[i], (target-nums[i], i))

nums = [2, 7, 11, 15]
target = 9
sol = Solution()
print sol.twoSum(nums, target)

This is a lot simpler in terms of complexity. The pointer goes through the array once, picking out each element and seeing what number needs to be paired with it to sum up to the target number.
Then, we put that in a dictionary. For example, element in index 0 would be stored as a key and it's leftover and index as a tuple for a value dict[2]:(7, 0).

Every time we look at an element we figure out if we have a corresponding number already in the dictionary, and if we do, then we return the index stored as well as the index we are currently on.
This make for an O(n) complexity.

Read More