973. K Closest Points to Origin

Medium : https://leetcode.com/problems/k-closest-points-to-origin/solution/

We have a list of `points`

on the plane. Find the `K`

closest points to the origin `(0, 0)`

.

(Here, the distance between two points on a plane is the Euclidean distance.)

You may return the answer in any order. The answer is guaranteed to be unique (except for the order that it is in.)

**Example 1:**

**Input: **points = [[1,3],[-2,2]], K = 1 **Output: **[[-2,2]] **Explanation: **The distance between (1, 3) and the origin is sqrt(10). The distance between (-2, 2) and the origin is sqrt(8). Since sqrt(8) < sqrt(10)…

https://leetcode.com/problems/repeated-substring-pattern/

Easy But **tough** for me as I do not know two of the algorithms

Given a non-empty string check if it can be constructed by taking a substring of it and appending multiple copies of the substring together. You may assume the given string consists of lowercase English letters only and its length will not exceed 10000.

**Example 1:**

**Input:** "abab"

**Output:** True

**Explanation:** It's the substring "ab" twice.

**Example 2:**

**Input:** "aba"

**Output:** False

**Example 3:**

**Input:** "abcabcabcabc"

**Output:** True

**Explanation:** It's the substring "abc" four times. (And the substring "abcabc" twice.)

**Solution:**

My intuition: We use the…

Medium — Leetcode: https://leetcode.com/problems/decoded-string-at-index/solution/

An encoded string `S`

is given. To find and write the *decoded* string to a tape, the encoded string is read **one character at a time** and the following steps are taken:

- If the character read is a letter, that letter is written onto the tape.
- If the character read is a digit (say
`d`

), the entire current tape is repeatedly written`d-1`

more times in total.

Now for some encoded string `S`

, and an index `K`

, find and return the `K`

-th letter (1 indexed) in the decoded string.

**Example 1:**

**Input: **S = "leet2code3", K…

Medium(https://leetcode.com/problems/populating-next-right-pointers-in-each-node/submissions/)

You are given a **perfect binary tree** where all leaves are on the same level, and every parent has two children. The binary tree has the following definition:

`struct Node {`

int val;

Node *left;

Node *right;

Node *next;

}

Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to `NULL`

.

Initially, all next pointers are set to `NULL`

.

**Follow up:**

- You may only use constant extra space.
- Recursive approach is fine, you may assume implicit stack space does not count as extra space…

Medium : https://leetcode.com/problems/binary-tree-right-side-view/

Given a binary tree, imagine yourself standing on the *right* side of it, return the values of the nodes you can see ordered from top to bottom.

**Example:**

Input:[1,2,3,null,5,null,4]Output:[1, 3, 4]Explanation:1 <---

/ \

2 3 <---

\ \

5 4 <---

**Solution**

**DFS vs. BFS**

There are two ways to traverse the tree: DFS *depth first search* and BFS *breadth first search*. Here is a small summary

BFS traverses level by level, and DFS first goes to the leaves.

Iterative — Easy : https://leetcode.com/problems/symmetric-tree/

Recursive — Medium [ very important and intuitive]

Hint : 1. A Tree is symmetric to itself. So if you implement a function which accepts two trees to check for symmetry, you can start the first call of the function with symmetric(root, root).

**Problem Statement:**

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree `[1,2,2,3,4,4,3]`

is symmetric:

`1`

/ \

2 2

/ \ / \

3 4 4 3

But the following `[1,2,2,null,3,null,3]`

is not:

`1 / \ 2 2 \…`

Easy

Sum of Left Leaves

Easy : https://leetcode.com/problems/sum-of-left-leaves/

Find the sum of all left leaves in a given binary tree.

**Example:**

3

/ \

9 20

/ \

15 7There are two left leaves in the binary tree, with values9and15respectively. Return24.

Iterative Code:

`# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def sumOfLeftLeaves(self, root: TreeNode) -> int: # 3:39 pm # a leaf is the one with no children # is must…`

Medium- Hard, https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/solution/

Given a binary tree, return the *zigzag level order* traversal of its nodes’ values. (ie, from left to right, then right to left for the next level and alternate between).

**During interview:**

- Its good to point out the differences in the space complexity of the BFS (using a queue) and DFS (recursion ) approaches.
- Both solutions are below.

For example:

Given binary tree `[3,9,20,null,null,15,7]`

,

` 3`

/ \

9 20

/ \

15 7

return its zigzag level order traversal as:

`[`

[3],

[20,9],

[15,7]

]

**Intuition,**

- It is quite evident that we are traversing one level at…

Following the previous post on BF traversal of BSTrees, here is another cool problem often can be easily described using two different data structures. A dictionary and a Tree at play. Please read along ..

Top view of a binary tree is the set of nodes visible when the tree is viewed from the top. Given a binary tree, print the top view of it. The output nodes can be printed in any order.

A node x is there in output if x is the topmost node at its horizontal distance. Horizontal distance of left child of a node x…

In this post, I will summarize a Binary’s Search Trees (BST)s, level order traversal. I picked this problem from HackerRank Site and feel like, its been touch based so much every where it needs a place where the problem and solution can be easily searched and read. So here we go…

Given a pointer to the root of a binary tree, you need to print the level order traversal of this tree. In level-order traversal, nodes are visited level by level from left to right. Complete the function and print the values in a single line separated by a space.

`…`

Currently preparing for interviews