# K Closest Points to Origin — Leetcode Medium

973. K Closest Points to Origin

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 = 1Output: [[-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), (-2, 2) is closer…`

# Repeated Substring Pattern: Leetcode tough KMP and Robin Karp Algorithm

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

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

# 2. Divisors + Rabin-Karp

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: TrueExplanation: It's the substring "ab" twice.`

Example 2:

`Input: "aba"Output: False`

Example 3:

`Input: "abcabcabcabc"Output: TrueExplanation: It's the substring "abc" four times. (And the substring "abcabc" twice.)`

Solution:

My intuition: We use the…

# Decoded String at Index : Array + math

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…`

# Populating Next Right Pointers in Each Node

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

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

# OVERVIEW BFS, Recursive DFS with Example : 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.

# LevelOrderTraversal : Symmetric Tree

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   / \…`

# Sum of left children — Preorder traversal

Easy

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 values 9 and 15 respectively. Return 24.`

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 = rightclass…`

# Binary Tree Zigzag Level Order Traversal

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:

1. Its good to point out the differences in the space complexity of the BFS (using a queue) and DFS (recursion ) approaches.
2. 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:

`[  ,  [20,9],  [15,7]]`

Intuition,

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

# Tree : Generate the Top- View of BST

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

# Problem

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…

# Tree : Level-Order-Traversal or Breath-First-Search

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…

# Problem

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.

# For example:

`…` ## Technical Interviews Preparation

Currently preparing for interviews