---
title: Introduction
description: Structured dependency spine based roadmap for solving DSA Problems on leetcode.
icon: play
---

## 1. Linear Structures

:::tip
Data is read in one direction, from the first item to the last. The current position is recorded at each step. All later phases use this skill.
:::

**[Hash Table](/hash-table)**

A key maps to a value in constant time, which removes the need for a full scan.

**[Prefix Sum](/prefix-sum)**

A running total is stored at each index, so the sum of any range is one subtraction.

**[Two Pointers](/two-pointers)**

Two indices move through the data from different positions and meet at the answer.

**[Sliding Window](/sliding-window)**

A range with a start and an end moves across the data, and the contents are updated at each step.

**[Binary Search](/binary-search)**

Half of a sorted range is removed at each step until the target is found.

**[Stack](/stack)**

Items are added and removed from one end, so the last item added is the first item removed.

**[Monotonic Stack](/monotonic-stack)**

A stack keeps its items in sorted order, which finds the next larger or smaller item in one pass.

## 2. Nodal & Grid

:::tip
The data is in separate parts. Each part points to the next part, or sits next to other parts on a flat surface. An index does not find the next item. The pointers or the neighbors give the path instead.
:::

**[Linked List](/linked-list)**

Each node points to the next node, and the pointers give the path through the data.

**[Hybrid Structures](/hybrid-structures)**

Two structures are combined, such as a hash map and a linked list, to get the best properties of each.

**[Matrix Index Math](/matrix-index-math)**

A two-dimensional grid is read as a flat array through a formula, and the neighbors are found by arithmetic.

## 3. Hierarchical

:::tip
Each part points to one or more parts below it. Those parts do the same. The method that solves a small part also solves the large part. This is recursion.
:::

**[Tree DFS](/tree-dfs)**

Each branch is followed to its end before the next branch is examined.

**[Tree BFS](/tree-bfs)**

All nodes at one level are visited before the nodes at the next level.

**[Binary Search Tree](/binary-search-tree)**

Each node holds a value that is larger than its left subtree and smaller than its right subtree.

**[Heap](/heap-priority-queue)**

The largest or smallest item is always at the top, and it is removed in logarithmic time.

**[Trie](/trie)**

Each node holds one character, and a path from the root spells a word.

## 4. Relational

:::tip
Each part can point to any other part. Loops can occur. The method must visit each part one time only. The order of the parts, or the distance between them, is not given in the data. The method finds it.
:::

**[Graph DFS](/graph-dfs)**

Each edge is followed to its end, and a visited set prevents a repeat visit.

**[Graph BFS](/graph-bfs)**

Nodes are visited in order of distance from the start, which gives the shortest path in an unweighted graph.

**[Topological Sort](/topological-sort)**

Nodes are put in an order where each node comes after all nodes that point to it.

**[Union-Find](/union-find)**

Two sets are merged and the set of any item is found in near-constant time.

## 5. Decision Space

:::tip
The data has no structure. The method makes one. Each choice makes a new branch. The problem sets the correct method: examine all branches, keep a record of the results already found, or make one choice and do not go back.
:::

**[Backtracking](/backtracking)**

Each choice makes a branch, and a branch is undone when it does not give a valid result.

**[1-D DP](/1d-dynamic-programming)**

The result for each state is stored in a list, and each new result is computed from the results before it.

**[Multi-D / Grid DP](/multi-d-grid-dp)**

The result for each state is stored in a table with two or more dimensions, and each cell is computed from its neighbors.

**[Greedy](/greedy)**

The best local choice is made at each step and is not changed later.

**[Intervals](/intervals)**

Ranges with a start and an end are sorted, and then merged, counted, or scheduled.