FlamingBytes

[Leetcode 136] Single Number

Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.

You must implement a solution with a linear runtime complexity and use only constant extra space.

What is a Monotonic Stack

A monotonic stack is a stack whose elements are monotonically increasing or decreasing. It contains all properties that a typical stack has and its elements are monotonic decreasing or increasing.

Monotonic increasing stack: [2 3 5 6 9]
Monotonic decreasing stack: [9 6 5 3 2]

Intro

A linked list is a data structure which represents a sequence of nodes. In a singly linked list, each node points to the next node. In a doubly linked list, each node points to both the next and previous node.

What is Greedy algorithm

Greedy is an algorithmic paradigm that builds up a solution piece by piece, always choosing the next piece that offers the most obvious and immediate benefit. So the problems where choosing locally optimal also leads to global solution are the best fit for Greedy.

What is backtracking

Backtracking is an algorithmic technique for solving problems recursively by trying to build a solution incrementally, one piece at a time, removing those solutions that fail to satisfy the constraints of the problem at any point in time (by time, here, is referred to the time elapsed till reaching any level of the search tree). Backtracking can also be said as an improvement to the brute force approach. So basically, the idea behind the backtracking technique is that it searches for a solution to a problem among all the available options.

What is Trie

A trie (pronounced as “try”) or prefix tree is a tree data structure used to efficiently store and retrieve keys in a dataset of strings. There are various applications of this data structure, such as autocomplete and spellchecker.

What is Graph Data Structure

A Graph is a non-linear data structure consisting of vertices and edges. The vertices are sometimes also referred to as nodes and the edges are lines or arcs that connect any two nodes in the graph. More formally a Graph is composed of a set of vertices( V ) and a set of edges( E ). The graph is denoted by G(E, V).

Intro

Binary Search Tree is a binary tree data structure which has the following properties:

• The left subtree of a node contains only nodes with values smaller than the node.
• The right subtree of a node contains only nodes with values greater than the node.
• The left and right subtree each must also be a binary search tree.
  Read more »

Intro

Binary Search splits the search space into two halves and only keep the half that has the search target and throw away the other half that would not have the target. In each step, the search space is reduced to half, until the target is found. Binary Search reduces the search time from linear O(n) to logarithmic O(log n).

Intro

A stack is a linear data structure that stores items in a Last-In/First-Out (LIFO) or First-In/Last-Out (FILO) manner. In stack, a new element is added at one end and an element is removed from that end only. The insert and delete operations are often called push and pop.