Tag: Algorithm

Last time we have talked about the pre-order traversal and post-order traversal of a binary tree (see here). Now let's look at another two traversals and how we can implement the traversal algorithm in C++. Let's first define the tree node here. For each node, we will have a value and two tree node pointers… Continue reading Tree Traversal (In-order / Level-order) →

Let’s continue… First, I want to cite a great explanation about tree traversal. There are generally two approaches related to tree traversal: BFS and DFS. Bread First Search (BFS): We scan through the tree level by level, following the order of height, from top to bottom. The nodes on higher level would be visited before… Continue reading Tree Traversal (preorder / postorder) →

Let's continue... Problem Statement: Word Break I Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words. Note: The same word in the dictionary may be reused multiple times in the segmentation. You may… Continue reading Word Break I && II →

Problem Statement: Unique Path I A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below). The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the… Continue reading Unique Path I && II (Recursion and Dynamic Programming) →

Problem Statement: Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand. (i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]). You are given a target value to search. If found in the array return its index, otherwise return -1. You may assume no duplicate exists in the array. Your algorithm's runtime complexity… Continue reading Search in Rotated Sorted Array →

Let’s continue… Problem Statement: Next Permutation Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers. If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order). The replacement must be in-place and use only constant extra memory. Here are some examples. Inputs… Continue reading Next Permutation and Longest Valid Parentheses →

Let’s continue… Problem Statement: Divide Two Integers Given two integers dividend and divisor, divide two integers without using multiplication, division and mod operator. Return the quotient after dividing dividend by divisor. The integer division should truncate toward zero. Example 1: Input: dividend = 10, divisor = 3 Output: 3 Example 2: Input: dividend = 7,… Continue reading Divide Two Integers and Sub String with Concatenation of All Words →

Let’s continue… Problem Statement: Swap Nodes in Pairs Given a linked list, swap every two adjacent nodes and return its head. Example: Given 1->2->3->4, you should return the list as 2->1->4->3. Note: Your algorithm should use only constant extra space. You may not modify the values in the list's nodes, only nodes itself may be changed.… Continue reading Swap Nodes in Pairs and Reverse Nodes in K Groups →

Let’s continue… Problem Statement: Merge K Sorted Lists Given a linked list, remove the n-th node from the end of list and return its head. Example: Given linked list: 1->2->3->4->5, and n = 2. After removing Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity. Example: Input:… Continue reading Merge K Sorted Lists →

Let’s continue… Problem Statement: Remove Nth Node from End of List Given a linked list, remove the n-th node from the end of list and return its head. 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… Continue reading Remove Nth Node from End of List and Generate Parentheses →

Let’s continue… Problem Statement: 4 Sums Given an array nums of n integers and an integer target, are there elements a, b, c, and d in nums such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target. Note: The solution set… Continue reading 4 sums and letter combinations of a phone number →

Let's continue... Problem Statement: 3 Sums Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero. Note: The solution set must not contain duplicate triplets. Example: Given array… Continue reading 3 Sums and 3 Sums Closest →