Leetcode (Python): Implement strStr()

Implement strStr().

Returns a pointer to the first occurrence of needle in haystack, or null if needle is not part of haystack.

Solution:

We first preprocess the needle, in such a way that we obtain the equivalent states, for instance:

   a a b a a b c
   0 0 1 0 1 2 3

That means that if we are have found aabaab, we have also found aab. When we process the haystack, when we arrive to a state that we cannot go on, we change to its previous equivalent state.

class Solution:
    # @param haystack, a string
    # @param needle, a string
    # @return a string or None
    def strStr(self, haystack, needle):
        if len(needle)==0:
            return haystack
        equivalentState=[0]
        previousState = 0;
        for i in range(1,len(needle)):
            equivalentState.append(previousState)
            if needle[previousState] == needle [i]:
                previousState += 1
            else:
                previousState = 0
        position = 0
        state = 0
        while position < len(haystack):
            if haystack[position] == needle[state]:
                position += 1
                state += 1
                if state == len(needle):
                    return haystack[position-state:]
            else:
                if state == 0:
                    position +=1
                else:
                    state = equivalentState[state]
        return None

LeetCode (Python): Remove Duplicates from Sorted Array

Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length.

Do not allocate extra space for another array, you must do this in place with constant memory.

For example,
Given input array A = [1,1,2],

Your function should return length = 2, and A is now [1,2].

Solution:

class Solution:
    # @param a list of integers
    # @return an integer
    def removeDuplicates(self, A):
        if len(A)==0:
            return 0
        end = 0;
        for i in range(1,len(A)):
            if A[i] != A[end]:
                end += 1
                self.swap(A,i,end)
        return end + 1
                
            
            
    def swap(self, A, pos1, pos2):
        temp = A[pos1]
        A[pos1] = A[pos2]
        A[pos2] = temp

LeetCode (Python): Binary Tree Inorder Traversal

Given a binary tree, return the inorder traversal of its nodes' values.
For example:
Given binary tree {1,#,2,3},

   1
    \
     2
    /
   3

return [1,3,2].
Note: Recursive solution is trivial, could you do it iteratively?

Solution

# Definition for a  binary tree node
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    # @param root, a tree node
    # @return a list of integers
    def inorderTraversal(self, root):
        stack = []
        node = root
        solution = []
        while node!= None or len(stack)>0:
            if node != None:
                stack.append(node)
                node = node.left
            else:
                node = stack.pop()
                solution.append(node.val)
                node = node.right
        return solution

Other solution:

This solution needs more space but is easier to understand.

# Definition for a  binary tree node
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    # @param root, a tree node
    # @return a list of integers
    def inorderTraversal(self, root):
        stack = []
        if root != None:
            stack.append(root)
        solution = []
        used = set()
        while len(stack)>0:
            node = stack.pop()
            if node in used:
                solution.append(node.val)
            else:
                used.add(node)
                if node.right != None:
                    stack.append(node.right)
                stack.append(node)
                if node.left != None:
                    stack.append(node.left)
        return solution

LeetCode (Python): Best Time to Buy and Sell Stock III

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete at most two transactions.

Note:

You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again). 

Solution

We can calculate the solution to the problem for 1 transaction, so we use dynamic programming calculating the solution to which is the maximum benefit prior and posterior to certain day, afterwards we just have to iterate through the sum of both arrays finding the maximum.

class Solution:
    # @param prices, a list of integer
    # @return an integer
    def maxProfit(self, prices):
        previousMin = float("infinity")
        nextMax = float("-infinity")
        maxProfitSellBefore = [0]
        maxProfitBuyAfter = [0] 
        for i in range(0,len(prices)):
            previousMin = min(previousMin, prices[i])
            if i>0:
                maxProfitSellBefore.append(max(maxProfitSellBefore[i-1], prices[i]-previousMin))
        for i in range(len(prices)-1,-1,-1):
            nextMax = max(nextMax, prices[i])
            if i<len(prices)-1:
                maxProfitBuyAfter.insert(0,max(maxProfitBuyAfter[0], nextMax-prices[i]))
        maxBenefit = 0
        for i in range(0,len(prices)):
            maxBenefit = max(maxBenefit, maxProfitSellBefore[i] + maxProfitBuyAfter[i])
        return maxBenefit

LeetCode (Python): Merge k Sorted Lists

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Divide and Conquer solution

We merge lists by pairs till we have only one list. The complexity is $O(n log(k))$.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    # @param a list of ListNode
    # @return a ListNode
    def mergeKLists(self, lists):
        if len(lists)==0:
            return None
        while len(lists)>1:
            nextLists = []
            for i in range(0,len(lists)-1,2):
                nextLists.append(self.mergeLists(lists[i],lists[i+1]))
            if len(lists)%2==1:
                nextLists.append(lists[len(lists)-1])
            lists = nextLists
        return lists[0]
        
    def mergeLists(self, list1, list2):
        dummy = ListNode(0)
        list = dummy
        while list1 != None and list2 != None:
            if list1.val < list2.val:
                list.next = list1
                list1 = list1.next
            else:
                list.next = list2
                list2 = list2.next
            list = list.next
        if list1 == None:
            list.next = list2
        else:
            list.next = list1
        return dummy.next

LeetCode: Binary Tree Inorder Traversal

Given a binary tree, return the inorder traversal of its nodes' values.
For example:
Given binary tree {1,#,2,3},

   1
    \
     2
    /
   3

return [1,3,2].
Note: Recursive solution is trivial, could you do it iteratively?

Solution

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        ArrayDeque<TreeNode> stack = new ArrayDeque<TreeNode>();
        List<Integer> solution = new ArrayList<Integer>();
        TreeNode node = root;
        while(!stack.isEmpty() || node !=null)
        {
            if (node != null)
            {
                stack.push(node);
                node = node.left;
            }
            else
            {
                node = stack.pop();
                solution.add(node.val);
                node = node.right;
            }
        }
        return solution;
    }
}

Other solution:

This solution needs more space but is easier to understand.

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        ArrayDeque<TreeNode> stack = new ArrayDeque<TreeNode>();
        List<Integer> solution = new ArrayList<Integer>();
        HashSet<TreeNode> used = new HashSet<TreeNode>();
        if(root!=null)
            stack.push(root);
        while(!stack.isEmpty())
        {
            TreeNode temp = stack.pop();
            if(used.contains(temp))
            {
                solution.add(temp.val);
                continue;
            }
            used.add(temp);
            if (temp.right != null)
                stack.push(temp.right);
            stack.push(temp);
            if (temp.left != null)
                stack.push(temp.left);
        }
        return solution;
    }
}

LeetCode (Python): Binary Tree Level Order Traversal II

Given a binary tree, return the bottom-up level order traversal of its nodes' values. (ie, from left to right, level by level from leaf to root).

For example:
Given binary tree {3,9,20,#,#,15,7},

    3
   / \
  9  20
    /  \
   15   7

return its bottom-up level order traversal as:

[
  [15,7]
  [9,20],
  [3],
]

Solution:

# Definition for a  binary tree node
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    # @param root, a tree node
    # @return a list of lists of integers
    def levelOrderBottom(self, root):
        solution = []
        thisLevel = []
        if root != None:
            thisLevel.append(root)
        while len(thisLevel)>0:
            levelNumbers = []
            nextLevel = []
            for node in thisLevel:
                levelNumbers.append(node.val)
                if node.left != None:
                    nextLevel.append(node.left)
                if node.right != None:
                    nextLevel.append(node.right)
            solution.insert(0,levelNumbers)
            thisLevel = nextLevel
        return solution

LeetCode (Python): Sudoku Solver

Write a program to solve a Sudoku puzzle by filling the empty cells.
Empty cells are indicated by the character '.'.
You may assume that there will be only one unique solution.

A sudoku puzzle...

...and its solution numbers marked in red. 

Solution

class Solution:
    # @param board, a 9x9 2D array
    # Solve the Sudoku by modifying the input board in-place.
    # Do not return any value.
    def solveSudoku(self, board):
        self.solveSudokuRec(board,0,0)
    
    def solveSudokuRec(self, board,row,col):
        if row == 9:
            return True
        if col == 8:
            nextRow = row +1
            nextCol = 0
        else:
            nextRow = row
            nextCol = col+1
        if board[row][col]!='.':
            return self.solveSudokuRec(board,nextRow,nextCol)
        for c in range(1,10):
            if self.canPut(board,str(c),row,col):
                board[row][col] = str(c)
                if self.solveSudokuRec(board,nextRow,nextCol):
                    return True
                board[row][col] = '.'
        return False
    
    def canPut(self, board, char, row, col):
        for i in range(0,9):
            if board[row][i] == char:
                return False
            if board[i][col] == char:
                return False
        rowGroup = (row//3) * 3
        colGroup = (col//3) * 3 
        for i in range(rowGroup, rowGroup+3):
            for j in range(colGroup, colGroup+3):
                if board[i][j] == char:
                    return False
        return True

LeetCode: Sudoku Solver

Write a program to solve a Sudoku puzzle by filling the empty cells.
Empty cells are indicated by the character '.'.
You may assume that there will be only one unique solution.

A sudoku puzzle...

...and its solution numbers marked in red. 

Solution

public class Solution {
    public void solveSudoku(char[][] board) {
       solveSudoku(board, 0,  0);
    }
    
    public boolean solveSudoku(char[][] board, int row, int col)
    {
        if (row == 9)
            return true;
        int nextRow = col == 8 ? row+1 : row;
        int nextCol = col == 8 ? 0 : col+1;
        if (board[row][col] !='.')
            return solveSudoku(board, nextRow, nextCol);
        for (char c='1'; c<='9'; c++)
        {
            if (canPut(board, c, row, col))
            {
                board[row][col] = c;
                if (solveSudoku(board, nextRow, nextCol))
                    return true;
                board[row][col] = '.';
            }
        }
        return false;
    }
    
    public boolean canPut(char[][] board, char c, int row, int col)
    {
        for(int i=0; i<9; i++)
        {
            if(board[row][i]==c)
                return false;
            if(board[i][col]==c)
                return false;
        }
        int startRowGroup = (row/3)*3;
        int startColGroup = (col/3)*3;
        for(int i=startRowGroup; i<startRowGroup+3; i++)
        {
            for(int j=startColGroup; j<startColGroup+3; j++)
                if(board[i][j]==c)
                    return false;
        }
        return true;
    }
    
}

LeetCode (Python): Sort List

Sort a linked list in O(n log n) time using constant space complexity.

Solution

As we are sorted a linked list, we need that our algorithm works efficiently  when we can only access the data sequentially. Of the three most common sorting algorithms, mergesort, quicksort and heapsort, mergesort is the one that performs better in this situation.
 

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    # @param head, a ListNode
    # @return a ListNode
    def sortList(self, head):
        if head == None:
            return None
        counter = 0 
        temp = head
        while temp != None:
            temp = temp.next
            counter += 1
        return self.sort(head, counter)
        
    def sort(self,head,size):
        if size ==1:
            return head
        list2 = head
        for i in range(0,size//2):
            list2 = list2.next
        list1 = self.sort(head, size//2)
        list2 = self.sort(list2,size-size//2)
        return self.merge(list1, size//2, list2, size-size//2)
        
    def merge(self,list1, sizeList1, list2, sizeList2):
        dummy = ListNode(0)
        list = dummy
        pointer1 = 0
        pointer2 = 0
        while pointer1 < sizeList1 and pointer2 < sizeList2:
            if list1.val<list2.val:
                list.next = list1
                list1 = list1.next
                pointer1 += 1
            else:
                list.next = list2
                list2 = list2.next
                pointer2 += 1
            list = list.next
        while pointer1 < sizeList1:
            list.next = list1
            list1 = list1.next
            pointer1 += 1
            list = list.next
        while pointer2 < sizeList2:
            list.next = list2
            list2 = list2.next
            pointer2 += 1
            list = list.next
        list.next = None
        return dummy.next

LeetCode (Python): Surrounded Regions

Given a 2D board containing 'X' and 'O', capture all regions surrounded by 'X'.

A region is captured by flipping all 'O's into 'X's in that surrounded region .

For example,

X X X X
X O O X
X X O X
X O X X

After running your function, the board should be:

X X X X
X X X X
X X X X
X O X X

Solution:

We use backtracking to identify the elements not surrounded by 'X' and we mark those with a temporal symbol ('$'). The elements not surrounded by 'X' means that exists a path of elements 'O' to a border. So we start the backtracking algorithm with the boarders.

The last thing is replacing the temporal element by 'O' and the rest elements to 'X'.

class Solution:
    # @param board, a 2D array
    # Capture all regions by modifying the input board in-place.
    # Do not return any value.
    def solve(self, board):
        if len(board)==0:
            return
        for row in range(0,len(board)):
            self.mark(board,row,0)
            self.mark(board,row,len(board[0])-1)
        for col in range(0, len(board[0])):
            self.mark(board, 0, col)
            self.mark(board, len(board)-1, col)
        
        for row in range(0,len(board)):
            for col in range(0, len(board[0])):
                if board[row][col]=='$':
                    board[row][col] = 'O'
                else:
                    board[row][col] = 'X'
        
    def mark(self, board, row, col):
        stack = []
        nCols= len(board[0])
        stack.append(row*nCols+col)
        while len(stack)>0:
            position = stack. pop()
            row = position // nCols
            col = position % nCols
            if board[row][col] != 'O':
                continue
            board[row][col] = '$'
            if row>0:
                stack.append((row-1)*nCols+col)
            if row< len(board)-1:
                stack.append((row+1)*nCols+col)
            if col>0: 
                 stack.append(row*nCols+col-1)
            if col < nCols-1:
                stack.append(row*nCols+col+1)

LeetCode (Python): Reorder List

Given a singly linked list L: L₀→L₁→…→L_n-1→L_n,
reorder it to: L₀→L_n→L₁→L_n-1→L₂→L_n-2→…
You must do this in-place without altering the nodes' values.
For example,
Given {1,2,3,4}, reorder it to {1,4,2,3}.

Solution:

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    # @param head, a ListNode
    # @return nothing
    def reorderList(self, head):
        if head == None:
            return head
        stack = []
        temp = head
        while temp != None:
            stack.append(temp)
            temp = temp.next
        list = head
        fromHead = head
        fromStack = True
        while (fromStack and list != stack[-1]) or ( not fromStack and list != fromHead):
            if fromStack:
                fromHead = fromHead.next
                list.next = stack.pop()
                fromStack = False
            else:
                list.next = fromHead
                fromStack = True
            list = list.next
        list.next = None

LeetCode (Python): Candy

There are N children standing in a line. Each child is assigned a rating value.

You are giving candies to these children subjected to the following requirements:

• Each child must have at least one candy.
• Children with a higher rating get more candies than their neighbors.

What is the minimum candies you must give?

Solution:

To obtain the number of candies per child, we pass the array in both directions. From left to right assures that if a child has higher rating than his left neighbor he will get more candies and from right to left for the opposite case. Afterwards we just have to sum the array. The running time is O(n).

class Solution:
    # @param ratings, a list of integer
    # @return an integer
    def candy(self, ratings):
        candies = [1]
        for i in range(1,len(ratings)):
            if ratings[i]>ratings[i-1]:
                candies.append(candies[i-1]+1)
            else:
                candies.append(1)
        sum = candies[len(ratings)-1]
        for i in range(len(ratings)-2,-1,-1):
            if ratings[i]>ratings[i+1]:
                candies[i] = max (candies[i], candies[i+1]+1)
            sum += candies[i]
        return sum

LeetCode (Python): Subsets

Given a set of distinct integers, S, return all possible subsets.

Note:

• Elements in a subset must be in non-descending order.
• The solution set must not contain duplicate subsets.

For example,
If S = [1,2,3], a solution is:

[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

Solution:

class Solution:
    # @param S, a list of integer
    # @return a list of lists of integer
    def subsets(self, S):
        S.sort()
        solution = []
        self.subsetsRec(S,0, [], solution)
        return solution
    
    def subsetsRec(self, S, index, tempSolution, solution):
        if index == len(S):
            solution.append(list(tempSolution))
        else:
            self.subsetsRec(S,index+1, tempSolution, solution)
            tempSolution.append(S[index])
            self.subsetsRec(S,index+1, tempSolution, solution)
            tempSolution.pop()

LeetCode (Python): Spiral Matrix

Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.

For example,
Given the following matrix:

[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]

You should return [1,2,3,6,9,8,7,4,5].

Solution:

class Solution:
    # @param matrix, a list of lists of integers
    # @return a list of integers
    def spiralOrder(self, matrix):
        solution = []
        if len(matrix)==0:
            return solution
        minRow = 0
        maxRow = len(matrix)-1
        minCol = 0 
        maxCol = len(matrix[0])-1
        row = 0
        col = 0
        state = 1
        if col == maxCol:
            state = 2
        while len(solution)<len(matrix) * len(matrix[0]):
            solution.append(matrix[row][col])
            if state == 1:
                col += 1
                if col == maxCol:
                    state = 2
                    minRow += 1
            elif state ==2:
                row += 1
                if row == maxRow:
                    state = 3
                    maxCol -= 1
            elif state ==3:
                col -= 1
                if col == minCol:
                    state = 4
                    maxRow -=1
            else:
                row -= 1
                if row == minRow:
                    state = 1
                    minCol += 1
        return solution

LeetCode (Python): Single Number II

Given an array of integers, every element appears three times except for one. Find that single one.
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory? 

Solution:

We keep tree variables: one with the bits that appear $3k+1$ times, two with those that appear $3k+2$, and three with $3k$, such that $k$ is an integer.

class Solution:
    # @param A, a list of integer
    # @return an integer
    def singleNumber(self, A):
        one = 0
        two = 0
        three = ~0
        for i in range(0, len(A)):
            nextOne = (one & ~A[i]) | (three & A[i])
            nextTwo = (two & ~A[i]) | ( one & A[i])
            nextThree = (three & ~A[i]) | (two & A[i])
            one = nextOne
            two = nextTwo
            three = nextThree
        return one

LeetCode: Single Number II

Given an array of integers, every element appears three times except for one. Find that single one.
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory? 

Solution:

We keep tree variables: one with the bits that appear $3k+1$ times, two with those that appear $3k+2$, and three with $3k$, such that $k$ is an integer.

public class Solution {
    public int singleNumber(int[] A) {
        int one = 0;
        int two = 0;
        int three = ~0;
        for(int i=0; i<A.length; i++)
        {
            int nextOne = (~A[i] & one) | (A[i] & three);
            int nextTwo = (~A[i] & two) | (A[i] & one);
            int nextThree = (~A[i] & three) | (A[i] & two);
            one = nextOne;
            two = nextTwo;
            three = nextThree;
        }
        return one;
    }
}

LeetCode (Python): Single Number

Given an array of integers, every element appears twice except for one. Find that single one.
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Solution:

class Solution:
    # @param A, a list of integer
    # @return an integer
    def singleNumber(self, A):
        temp = 0
        for i in range(0,len(A)):
            temp ^= A[i]
        return temp

LeetCode: Single Number

Given an array of integers, every element appears twice except for one. Find that single one.
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Solution:

public class Solution {
    public int singleNumber(int[] A) {
        int temp = A[0];
        for(int i=1; i<A.length; i++)
            temp^=A[i];
        return temp;
    }
}

LeetCode (Python): 3Sum Closest

Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

    For example, given array S = {-1 2 1 -4}, and target = 1.
    The sum that is closest to the target is 2. (-1 + 2 + 1 = 2). 

Solution:

class Solution:
    # @return an integer
    def threeSumClosest(self, num, target):
        num.sort()
        error = float("infinity")
        if len(num)<3:
            return 0
        for i in range(0, len(num)-2):
            begin = i+1
            end = len(num)-1
            while begin<end:
                if abs(num[i]+num[begin]+num[end]-target) < error:
                    error = abs(num[i]+num[begin]+num[end]-target)
                    solution = num[i]+num[begin]+num[end]
                if num[i]+num[begin]+num[end] > target:
                    end -= 1
                else:
                    begin += 1
        return solution

LeetCode (Python): Binary Tree Level Order Traversal

Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).
For example:
Given binary tree {3,9,20,#,#,15,7},

    3
   / \
  9  20
    /  \
   15   7

return its level order traversal as:

[
  [3],
  [9,20],
  [15,7]
]

Solution:

# Definition for a  binary tree node
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    # @param root, a tree node
    # @return a list of lists of integers
    def levelOrder(self, root):
        solution=[]
        if root == None:
            return solution
        levelToProcess =[root]
        while len(levelToProcess)>0:
            numbersLevel =[]
            nextLevel = []
            for temp in levelToProcess:
                numbersLevel.append(temp.val)
                if temp.left != None:
                    nextLevel.append(temp.left)
                if temp.right != None:
                    nextLevel.append(temp.right)
            solution.append(numbersLevel)
            levelToProcess = nextLevel
        return solution

Leetcode: Binary Tree Level Order Traversal

Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).
For example:
Given binary tree {3,9,20,#,#,15,7},

    3
   / \
  9  20
    /  \
   15   7

return its level order traversal as:

[
  [3],
  [9,20],
  [15,7]
]

Solution:

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> solution = new ArrayList<List<Integer>>();
        if (root == null)
            return solution;
        List<TreeNode> actualList = new ArrayList<TreeNode>();
        actualList.add(root);
        while(!actualList.isEmpty())
        {
            ArrayList<Integer> thisLevel = new ArrayList<Integer>();
            List<TreeNode> nextList = new ArrayList<TreeNode>();
            for(TreeNode temp: actualList)
            {
                thisLevel.add(temp.val);
                if(temp.left!=null)
                    nextList.add(temp.left);
                if(temp.right!=null)
                    nextList.add(temp.right);
            }
            solution.add(thisLevel);
            actualList = nextList;
        }
        return solution;
    }
}

LeetCode (Python): Linked List Cycle II

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.
Follow up:
Can you solve it without using extra space?

Solution:

We first detect if a cycle exists, as Linked List Cycle I. Then we keep a pointer in the same position and obtain the length of the loop. With that we just have to keep the fast pointer this amount of positions in advance and they will always cross where the cycle starts.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    # @param head, a ListNode
    # @return a list node
    def detectCycle(self, head):
        if head == None or head.next == None:
            return None
        slowPointer = head
        fastPointer = head.next
        while fastPointer !=None and fastPointer.next!= None and fastPointer != slowPointer:
            fastPointer = fastPointer.next.next
            slowPointer = slowPointer.next
        if fastPointer != slowPointer:
            return None
        cycleSize = 1
        fastPointer = fastPointer.next
        while fastPointer != slowPointer:
            fastPointer = fastPointer.next
            cycleSize += 1
        fastPointer = head
        for i in xrange(0,cycleSize):
            fastPointer = fastPointer.next
        slowPointer = head
        while fastPointer != slowPointer:
            fastPointer = fastPointer.next
            slowPointer = slowPointer.next
        return fastPointer

LeetCode: 3Sum Closest

Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

    For example, given array S = {-1 2 1 -4}, and target = 1.
    The sum that is closest to the target is 2. (-1 + 2 + 1 = 2). 

Solution:

public class Solution {
    public int threeSumClosest(int[] num, int target) {
        Arrays.sort(num);
        int closest = 0;
        int error = Integer.MAX_VALUE;
        for(int i =0; i< num.length-2; i++)
        {
            int begin = i+1;
            int end = num.length-1;
            while(begin<end)
            {
                if( Math.abs(num[i]+num[begin]+num[end]-target)<error)
                {
                    error = Math.abs(num[i]+num[begin]+num[end]-target);
                    closest = num[i]+num[begin]+num[end];
                }
                if(num[i]+num[begin]+num[end]>target)
                    end--;
                else
                    begin++;
            }
        }
        return closest;
    }
}

LeetCode: Linked List Cycle II

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.
Follow up:
Can you solve it without using extra space?

Solution:

We first detect if a cycle exists, as Linked List Cycle I. Then we keep a pointer in the same position and obtain the length of the loop. With that we just have to keep the fast pointer this amount of positions in advance and they will always cross where the cycle starts.

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        int states = 0;
        if (head == null || head.next == null)
            return null;
        ListNode slowPointer = head;
        ListNode fastPointer = head.next;
        while(fastPointer!=null && fastPointer.next != null && fastPointer!=slowPointer)
        {
            fastPointer = fastPointer.next.next;
            slowPointer = slowPointer.next;
        }
        if (fastPointer != slowPointer)
            return null;
        int counter = 1;
        fastPointer = fastPointer.next;
        while(fastPointer!=slowPointer)
        {
            fastPointer = fastPointer.next;
            counter++;
        }
        fastPointer = head;
        for (int i=0; i< counter; i++)
            fastPointer = fastPointer.next;
        slowPointer = head;
        while(fastPointer!=slowPointer)
        {
            fastPointer = fastPointer.next;
            slowPointer = slowPointer.next;
        }
        return fastPointer;
    }
}

LeetCode (Python): Climbing Stairs

You are climbing a stair case. It takes n steps to reach to the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Solution:

class Solution:
    # @param n, an integer
    # @return an integer
    def climbStairs(self, n):
        before2 = 0
        before1 = 1
        for i in range(0,n):
            temp = before2 + before1
            before2 = before1
            before1 = temp
        return before1

LeetCode: Climbing Stairs

You are climbing a stair case. It takes n steps to reach to the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Solution:

public class Solution {
    public int climbStairs(int n) {
        int before2 = 0;
        int before1 = 1;
        for(int i=0; i<n; i++)
        {
            int temp = before2 +before1;
            before2 = before1;
            before1 = temp;
        }
        return before1;
    }
}

LeetCode: Construct Binary Tree from Inorder and Postorder Traversal

Given inorder and postorder traversal of a tree, construct the binary tree.
Note:
You may assume that duplicates do not exist in the tree.

Solution:

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        return buildTree(inorder, postorder, inorder.length, 0, 0);
    }
    
    public TreeNode buildTree(int[] inOrder, int[] postOrder, int nElements, int startInOrder, int startPostOrder) 
    {
        if (nElements==0)
            return null;
        int rootVal = postOrder[startPostOrder+nElements-1];
        TreeNode root = new TreeNode(rootVal);
        if(nElements==1)
            return root;
        for(int i=0; i<nElements; i++)
        {
            if(inOrder[startInOrder+i]==rootVal)
            {
                root.left =  buildTree(inOrder, postOrder, i, startInOrder, startPostOrder);
                root.right =  buildTree(inOrder, postOrder, nElements-i-1, startInOrder+i+1, startPostOrder+i);
                break;
            }
        }
        return root;
    }
}

LeetCode (Python): Binary Tree Maximum Path Sum

Given a binary tree, find the maximum path sum.

The path may start and end at any node in the tree.

For example:
Given the below binary tree,

       1
      / \
     2   3

Return 6.

Solution:

# Definition for a  binary tree node
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    # @param root, a tree node
    # @return an integer
    def maxPathSum(self, root):
        self.maxValue = float("-inf")
        self.maxPathSumRec(root)
        return self.maxValue
    
    def maxPathSumRec(self, root):
        if root == None:
             return 0
        leftSum = self.maxPathSumRec(root.left)
        rightSum = self.maxPathSumRec(root.right)
        if leftSum<0 and rightSum<0:
            self.maxValue = max(self.maxValue, root.val)
            return root.val
        if leftSum>0 and rightSum>0:
            self.maxValue = max(self.maxValue, root.val+leftSum+rightSum)
        maxValueUp = max(leftSum, rightSum) +root.val
        self.maxValue = max(self.maxValue, maxValueUp)
        return maxValueUp

LeetCode (Python): 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.

Solution:

class Solution:
    # @return a boolean
    def isValid(self, s):
        stack = []
        for i in range(0, len(s)):
            if s[i] == '(' or s[i] == '[' or s[i] == '{':
                stack.append(s[i])
            else:
                if len(stack)==0:
                    return False
                lastOpenParenthesis = stack.pop()
                if (s[i]==')' and lastOpenParenthesis !='(') or (s[i]==']' and lastOpenParenthesis !='[') or (s[i]=='}' and lastOpenParenthesis !='{'):
                    return False
        return len(stack)==0

LeetCode: 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.

Solution:

public class Solution {
    public boolean isValid(String s) {
        ArrayDeque<Character> stack = new ArrayDeque<Character>();
        for (int i=0; i<s.length(); i++)
        {
            if(s.charAt(i)=='(' || s.charAt(i)=='[' || s.charAt(i)=='{')
                stack.push(s.charAt(i));
            else 
            {
                if(stack.isEmpty())
                    return false;
                char lastOpenParenthesis = stack.pop();
                if((s.charAt(i)==')' && lastOpenParenthesis!= '(') || (s.charAt(i)==']' && lastOpenParenthesis!= '[') || 
                (s.charAt(i)=='}' && lastOpenParenthesis!= '{'))
                    return false;
            }
        }
        return stack.isEmpty();
        
    }
}

LeetCode (Python): Pascal's Triangle II

Given an index k, return the k^th row of the Pascal's triangle.
For example, given k = 3,
Return [1,3,3,1].
Note:
Could you optimize your algorithm to use only O(k) extra space?

Solution:

class Solution:
    # @return a list of integers
    def getRow(self, rowIndex):
        actualRow =[1]
        for row in range(0, rowIndex):
            previousRow = actualRow
            actualRow = [1]
            for i in range(1,len(previousRow)):
                actualRow.append(previousRow[i-1] + previousRow[i])
            actualRow.append(1)
        return actualRow

LeetCode: Pascal's Triangle II

Given an index k, return the k^th row of the Pascal's triangle.
For example, given k = 3,
Return [1,3,3,1].
Note:
Could you optimize your algorithm to use only O(k) extra space?

Solution:

public class Solution {
    public List<Integer> getRow(int rowIndex) {
        List<Integer> actualRow = new ArrayList<Integer>();
         actualRow.add(1);
       
        for(int row=0; row<rowIndex; row++)
        {
            List<Integer> previousRow = actualRow;
            actualRow = new ArrayList<Integer>();
            actualRow.add(1);
            for(int i=1; i< previousRow.size(); i++)
            {
                actualRow.add(previousRow.get(i-1) + previousRow.get(i));
            }
            actualRow.add(1);
        }
        return actualRow;
    }
}

LeetCode (Python): Longest Consecutive Sequence

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.
For example,
Given [100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.
Your algorithm should run in O(n) complexity.

Solution:

We use a bimap to keep the intervals, implemented with two hashmaps one that starts are mapped to ends and the other one viceversa.

class Solution:
    # @param num, a list of integer
    # @return an integer
    def longestConsecutive(self, num):
        startToEnd = {}
        endToStart = {}
        longest = 0
        for i in range(0, len(num)):
            start = num[i]
            end = num[i]
            if num[i] in startToEnd:
                end = startToEnd[num[i]]
                del startToEnd[num[i]]
                del endToStart[end]
            if num[i] in endToStart:
                start = endToStart[num[i]]
                del startToEnd[start]
                del endToStart[num[i]]
            if num[i]-1 in endToStart:
                start = min(start, endToStart[num[i]-1])
                del startToEnd[endToStart[num[i]-1]]
                del endToStart[num[i]-1]
            if num[i]+1 in startToEnd:
                end = max(end, startToEnd[num[i]+1])
                del endToStart[startToEnd[num[i]+1]]
                del startToEnd[num[i]+1]
            startToEnd[start] = end
            endToStart[end] = start
            longest = max(longest, end-start+1)
        return longest

LeetCode: Longest Consecutive Sequence

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.
For example,
Given [100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.
Your algorithm should run in O(n) complexity.

Solution:

We use a bimap to keep the intervals, implemented with two hashmaps one that starts are mapped to ends and the other one viceversa.

public class Solution {
    public int longestConsecutive(int[] num) {
        int longest=0;
        HashMap<Integer, Integer> startToEnd = new HashMap<Integer, Integer>();
        HashMap<Integer, Integer> endToStart = new HashMap<Integer, Integer>();
        for(int i =0; i<num.length; i++)
        {
            int start = num[i];
            int end = num[i];
            if(endToStart.containsKey(num[i]))
            {
                start = endToStart.get(num[i]);
                startToEnd.remove(start);
                endToStart.remove(num[i]);
            }
            if(startToEnd.containsKey(num[i]))
            {
                end = startToEnd.get(num[i]);
                startToEnd.remove(num[i]);
                endToStart.remove(end);
            }
            if(endToStart.containsKey(num[i]-1))
            {
                start = Math.min(start, endToStart.get(num[i]-1));
                startToEnd.remove(start);
                endToStart.remove(num[i]-1);
            }
            if(startToEnd.containsKey(num[i]+1))
            {
                end = Math.max(end, startToEnd.get(num[i]+1));
                startToEnd.remove(num[i]+1);
                endToStart.remove(end);
            }
            startToEnd.put(start,end);
            endToStart.put(end,start);
            longest = longest < end- start + 1 ? end- start + 1 : longest;
        }
        return longest;
    }
}

LeetCode (Python): Scramble String

Given a string s1, we may represent it as a binary tree by partitioning it to two non-empty substrings recursively.

Below is one possible representation of s1 = "great":

    great
   /    \
  gr    eat
 / \    /  \
g   r  e   at
           / \
          a   t

To scramble the string, we may choose any non-leaf node and swap its two children.

For example, if we choose the node "gr" and swap its two children, it produces a scrambled string "rgeat".

    rgeat
   /    \
  rg    eat
 / \    /  \
r   g  e   at
           / \
          a   t

We say that "rgeat" is a scrambled string of "great".

Similarly, if we continue to swap the children of nodes "eat" and "at", it produces a scrambled string "rgtae".

    rgtae
   /    \
  rg    tae
 / \    /  \
r   g  ta  e
       / \
      t   a

We say that "rgtae" is a scrambled string of "great".

Given two strings s1 and s2 of the same length, determine if s2 is a scrambled string of s1.

Solution:

We use a top-down dynamic approach where we need a 3D array to keep the information, hence the memory complexity is $O(n^3)$.

class Solution:
    # @return a boolean
    def isScramble(self, s1, s2):
        if len(s1)!=len(s2):
            return False
            
        isScramble=[]
        for i in range(0,len(s1)):
            isScramble.append([])
            for j in range(0, len(s1)):
                isScramble[i].append([])
                for k in range(0, len(s1)):
                    isScramble[i][j].append(None)
        return self.isScrambleRec(s1, s2, 0, 0, len(s1)-1, isScramble)
        
    def isScrambleRec(self, s1, s2, i1, i2, length, isScramble):
        if isScramble[i1][i2][length] != None:
            return isScramble[i1][i2][length]
        if length==0:
            isScramble[i1][i2][length] = (s1[i1]==s2[i2])
        else:
            valid = False
            for l in range(0, length):
                valid = valid 

                  or (self.isScrambleRec(s1,s2,i1,i2,l, isScramble) and self.isScrambleRec(s1,s2,i1+l+1,i2+l+1,length-l-1, isScramble))

                  or (self.isScrambleRec(s1,s2,i1,i2+length-l,l, isScramble) and self.isScrambleRec(s1,s2,i1+l+1,i2,length-l-1, isScramble))
            isScramble[i1][i2][length] = valid
        return isScramble[i1][i2][length]

LeetCode (Python): ZigZag Conversion

The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

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

We add another example to clarify, same string with 4 rows

P     I     N
A   L S   I G
Y A   H R   
P     I 

convert("PAYPALISHIRING", 4) should return "PINALSHIGYAHRPI"

Solution:

class Solution:
    # @return a string
    def convert(self, s, nRows):
        if nRows == 1:
            return s
        solution = []
        for i in range(0, nRows):
            count = i
            step1 = 2*(nRows-1-i)
            step2 = 2*i
            while count < len(s):
                solution.append(s[count])
                if step1 > 0 and step2 > 0 and count+step1<len(s):
                    count += step1
                    solution.append(s[count])
                    count += step2
                else:
                    count +=(step1+step2)
        return "".join(solution)

LeetCode (Python): Palindrome Partitioning

Given a string s, partition s such that every substring of the partition is a palindrome.

Return all possible palindrome partitioning of s.

For example, given s = "aab",
Return

  [
    ["aa","b"],
    ["a","a","b"]
  ]

Solution:

We can use dynamic programming to calculate all the possible substrings if they are palindrome or not and save them in a matrix. Then we use backtracking to generate all the possible partitions.

class Solution:
    # @param s, a string
    # @return a list of lists of string
    def partition(self, s):
        isPalindrome = []
        for start in range(0, len(s)):
            isPalindrome.append([])
            
        for length in range(0, len(s)):
            for start in range(0,len(s)-length):
                if length==0:
                    isPalindrome[start].append(True)
                elif length == 1:
                    isPalindrome[start].append(s[start]==s[start+length])
                else:
                    isPalindrome[start].append(isPalindrome[start+1][length-2] and s[start]==s[start+length])
        
        solution = []
        self.partitionRec(s,0,isPalindrome, [], solution)
        return solution
    
    def partitionRec(self,s,index, isPalindrome, tempSolution, solution):
        if index==len(s):
            solution.append(list(tempSolution))
        
        for length in range(0, len(s)-index):
            if isPalindrome[index][length]:
                tempSolution.append(s[index:index+length+1])
                self.partitionRec(s,index+length+1,isPalindrome, tempSolution, solution)
                tempSolution.pop()

Leetcode: Search in Rotated Sorted Array II

Follow up for "Search in Rotated Sorted Array":
What if duplicates are allowed?
Would this affect the run-time complexity? How and why?
Write a function to determine if a given target is in the array.

Solution:

In this example, we cannot do any better than $O(n)$ as we can have $n-1$ identical elements and the other being the target. In this case the target could be in any position. Hence, traversing the array is the best we can do.

public class Solution {
    public boolean search(int[] A, int target) {
        for (int i=0; i<A.length; i++)
        {
            if(A[i]==target)
                return true;
        }
        return false;
    }
}

LeetCode (Python): Search in Rotated Sorted Array II

Follow up for "Search in Rotated Sorted Array":
What if duplicates are allowed?
Would this affect the run-time complexity? How and why?
Write a function to determine if a given target is in the array.

Solution:

In this example, we cannot do any better than $O(n)$ as we can have $n-1$ identical elements and the other being the target. In this case the target could be in any position. Hence, traversing the array is the best we can do.

class Solution:
    # @param A a list of integers
    # @param target an integer
    # @return a boolean
    def search(self, A, target):
        for i in xrange(0, len(A)):
            if A[i]==target:
                return True
        return False

LeetCode (Python): Palindrome Partitioning II

Given a string s, partition s such that every substring of the partition is a palindrome.

Return the minimum cuts needed for a palindrome partitioning of s.

For example, given s = "aab",
Return 1 since the palindrome partitioning ["aa","b"] could be produced using 1 cut.

Solution:

We use dynamic programming twice, first we obtain the matrix that indicates if an element is palindrome (cf. Palindrome Partioning I). Then, we calculate the minCut till the element i, as follows:

•  If isPalindrome(0,i) then minCut[i]=0
• else minCut[i] = min( minCut[j]+1 && isPalindrome(i,j))

class Solution:
    # @param s, a string
    # @return an integer
    def minCut(self, s):
        isPalindrome=[]
        for start in range(0, len(s)):
            isPalindrome.append([])
            
        for length in range(0,len(s)):
            for start in range(0, len(s)-length):
                if length == 0:
                    isPalindrome[start].append(True)
                elif length == 1:
                    isPalindrome[start].append(s[start]==s[start+1])
                else:
                    isPalindrome[start].append(isPalindrome[start+1][length-2] and s[start]==s[start+length])
                    
        minCut = []
        for i in range(0, len(s)):
            if isPalindrome[0][i]:
                minCut.append(0)
            else:
                minCut.append(minCut[i-1]+1)
            for j in range(0,i):
                if isPalindrome[j+1][i-j-1]:
                    minCut[i] = min(minCut[j]+1,minCut[i])
        return minCut[len(s)-1]

LeetCode (Python): Generate Parentheses

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
For example, given n = 3, a solution set is:
"((()))", "(()())", "(())()", "()(())", "()()()"

Solution:

class Solution:
    # @param an integer
    # @return a list of string
    def generateParenthesis(self, n):
        solution = []
        self.generateParenthesisRec(n,0,0,[],solution)
        return solution
    
    def generateParenthesisRec(self, n, openParentheses, closeParentheses,tempSolution,solution):
        if closeParentheses == n:
            solution.append(''.join(tempSolution))
            return
        if openParentheses<n:
            tempSolution.append('(')
            self.generateParenthesisRec(n,openParentheses+1,closeParentheses,tempSolution,solution)
            tempSolution.pop()
        if closeParentheses<openParentheses:
            tempSolution.append(')')
            self.generateParenthesisRec(n,openParentheses,closeParentheses+1,tempSolution,solution)
            tempSolution.pop()

LeetCode (Python): Longest Valid Parentheses

Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.
For "(()", the longest valid parentheses substring is "()", which has length = 2.
Another example is ")()())", where the longest valid parentheses substring is "()()", which has length = 4.

Solution:

class Solution:
    # @param s, a string
    # @return an integer
    def longestValidParentheses(self, s):
        stack = []
        lastError = -1
        longestValidParentheses = 0
        for i in range(0, len(s)):
            if s[i] =='(':
                stack.append(i)
            else:
                if len(stack) == 0:
                    lastError = i;
                else:
                    stack.pop()
                    if len(stack)==0:
                        validTill = lastError
                    else:
                         validTill = stack[-1]
                    longestValidParentheses = max(longestValidParentheses, i-validTill)
        return longestValidParentheses

LeetCode (Python): Simplify Path

Given an absolute path for a file (Unix-style), simplify it.
For example, path = "/home/", => "/home" path = "/a/./b/../../c/", => "/c"


Corner Cases:

• Did you consider the case where path = "/../"?
  In this case, you should return "/".
• Another corner case is the path might contain multiple slashes '/' together, such as "/home//foo/".
  In this case, you should ignore redundant slashes and return "/home/foo".

Soultion:

class Solution:
    # @param path, a string
    # @return a string
    def simplifyPath(self, path):
        folders = path.split('/')
        used = []
        for i in range(0, len(folders)):
            if folders[i]=='.':
                used.append(False)
            elif folders[i]=='..':
                used.append(False)
                for j in range(i-1,-1,-1):
                    if used[j]:
                        used[j] = False
                        break
            elif len(folders[i])==0:
                used.append(False)
            else:
                used.append(True)
        solution = []
        
        for i in range(0, len(folders)):
            if used[i]:
                solution.append('/')
                solution.append(folders[i])
        
        if len(solution) == 0:
            solution.append('/')
            
        return ''.join(solution)

LeetCode (Python): Subsets II

Given a collection of integers that might contain duplicates, S, return all possible subsets.

Note:

• Elements in a subset must be in non-descending order.
• The solution set must not contain duplicate subsets.

For example,
If S = [1,2,2], a solution is:

[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

Solution:

class Solution:
    # @param num, a list of integer
    # @return a list of lists of integer
    def subsetsWithDup(self, S):
        S.sort()
        solution = [] 
        self.subsetsWithDupRec(S, 0, [], solution)
        return solution
        
    def subsetsWithDupRec(self, S, index, tempSolution, solution):
        if index== len(S):
            solution.append(list(tempSolution))
            return
        
        #Not adding this element
        i = index
        while i<len(S) and S[i]==S[index]:
            i += 1
        self.subsetsWithDupRec(S, i, tempSolution, solution)
        
        #Adding it
        tempSolution.append(S[index])
        self.subsetsWithDupRec(S, index+1, tempSolution, solution)
        tempSolution.pop()

LeetCode (Python): Remove Duplicates from Sorted Array II

Follow up for "Remove Duplicates":
What if duplicates are allowed at most twice?

For example,
Given sorted array A = [1,1,1,2,2,3],

Your function should return length = 5, and A is now [1,1,2,2,3].

Solution:

We can obtain an algorithm that runs in $O(n)$ if we use an extra $O(n)$ space.

class Solution:
    # @param A a list of integers
    # @return an integer
    def removeDuplicates(self, A):
        aCopy =[]
        count = 0
        value = float("-infinity")
        for i in range(0, len(A)):
            if A[i] == value:
                count +=1
            else:
                count = 1
                value = A[i]
            if count <=2:
                aCopy.append(A[i])
        for i in range(0,len(aCopy)):
            A[i] = aCopy[i]
        return len(aCopy)