Contains Duplicate III

problem

Given an array of integers, find out whether there are two distinct indices i and j in the array such that the absolute difference between nums[i] and nums[j] is at most t and the absolute difference between i and j is at most k.

how to solve

To solve this problem, I use set(binary search tree). In set, the value is sorted automatically and I can insert and delete in O(logn). We can check the most near higher element and the most near lower element in O(logn) using lower_bound. So we can get answer in O(nlogn).

code

Validate BST

problem

Implement a function to check if a binary tree is a binary search tree.

how to solve

Binary search tree means that all left nodes must be less than or equal to the current node and all right nodes must be more than or equal to the current node. So we have to check this condition to preserve the min and max value. When we branch left , the max gets updated. When we branch right, the min gets updated. If anything fails these checks, we stop and return false.

code

Check Balanced

problem

Implement a function to check if a binary tree is balanced.

how to solve

A balanced tree is defined to be a tree such that the heights of the two subtrees of any node never differ by more than one. So I implement a function fetchHeight to get the heights of subtrees. To use a past result of fetchHeight function, I used hash table. If I calculate the height once before. I can get this value in O(1). To calculate the all of the value of fetch Height function, I firstly traverse all nodes in O(n). Next, I can check the all subtree to meet the definition of a balanced tree to answer this question.

code

Intersection

problem

Write a program to find the node at which the intersection of two singly linked lists begins. - If the two linked lists have no intersection at all, return null.

• The linked lists must retain their original structure after the function returns.
• You may assume there are no cycles anywhere in the entire linked structure.
• Your code should preferably run in O(n) time and use only O(1) memory.

how to solve

Firstly, I calculate the length of two linked list and advance the pointer by the difference in lengths. Secondly, traverse on each linked list until the pointers are the same.

code

Loop Detection

problem

Given a circular linked list, implement an algorithm that returns the node at the beginning of the loop.

how to solve

If I can use extra space, I can solve this very easily. I can justly use a hash table to detect if the element is appeared or not.

Next, I want to consider this problem without using that data structure. I took the following steps.

• Create two pointers, FastPointer and SlowPointer.
• Move fastPointer at a rate of 2 steps and SlowPointer at a rate of 1 step.
• When they collide, move SlowPointer to LinkedListHead. Keep FastPointer where it is.
• Move Slow Pointer and FastPointer at a rate of one step. Return the new collision point

code1

without using extra space.

code2(with using map)

with using hash map.

srm707 medium StepsConstruct

problem

There is a rectangular board that is divided into n rows by m columns of cells. Each cell is either empty or it contains an obstacle. You are given the description of the board in the board. Each character in board represents one cell. More precisely, the character board[i][j] represents the cell at coordinates (row i, column j). The character ‘#’ represents an obstacle, the character ‘.’ is an empty cell.

You would like to travel from the top left corner to the bottom right corner of the board in exactly k steps. More precisely, you want to perform the following sequence of actions:

Enter the board by stepping onto the cell at coordinates (0, 0): the top left corner. Make exactly k steps. In each step, you’ll move from your current cell to one of the cells that share a side with your current cell. In other words, in each step you’ll go one cell up, down, left, or right. After the k-th step, you must be in the bottom right corner: at coordinates (n-1, m-1). Note that you can only step onto empty cells. You have to move in each step, it is not allowed to stay in the same cell. You are allowed to visit each empty cell arbitrarily many times. You are not allowed to leave the board while making the k steps.

You are given the board and the k. Determine whether it is possible to reach the bottom right corner in the way described above. If there is no solution, return an empty . If there are some solutions, choose any one of them and return a containing its description.

If a solution exists, the returned should consist of k characters, each describing one step. Each character should be one of ‘U’ (up), ’D' (down), ‘L’ (left), and ‘R’ (right).

how to solve

I can solve this problem by using bfs search. There is some points to solve this problem. Firstly, the parity of step is same as the sum of the goal point’s x and y. So If I can find the goal route, and this step’s parity is same as the parity of k, I can get the way to reach the goal by k step.

code

srm707 easy Cross

problem

There is a rectangular board that is divided into n rows by m columns of cells. Each cell is either black or white. You are given the description of the board in the board. Each character in board represents one cell. More precisely, the character board[i][j] represents the cell at coordinates (row i, column j). The character ‘#’ represents a black cell, the character ‘.’ is a white cell. Formally, there is a cross centered at (x, y) if the following five cells are all black: (x, y), (x+1, y), (x-1, y), (x, y-1), and (x, y+1). Note that other cells adjacent to the cross may also be black, it is still a valid cross.

Return “Exists” if there is at least one cross on the given board. Otherwise, return “Does not exist”. Note that the return value is case-sensitive.

code