On-Discrete-DS

Algorithms for Discrete Data Structures

This repository contains solutions to a wide collection of algorithmic and data structure problems, organized by difficulty and sub-level. Each problem resides in its own folder and includes a dedicated README describing its statement, constraints and solution.

Structure

The repository is divided into four main difficulty categories:

• Easy
• Moderate
• Challenging
• Hard

Each of these folders contains subfolders representing individual problems, named with a suffix (Lvl N) - where N indicates the relative sublevel of difficulty within that category (Lvl 1 being simpler than higher levels).

Example:

1-Easy/
  ├── Correct Bracket Sequence (Lvl 1)/
  └── Maximum Period (Lvl 4)/

3-Challenging/
  ├── Segments with Sum in a Range (Lvl 1)/
  └── The Sliding k-th Statistic (Lvl 3)/

4-Hard/
  ├── Number of Distinct Substrings (Lvl 2)/
  └── Fuzzy Dictionary (Lvl 4)/

Each task folder includes:

• README.md - problem description and implementation notes
• solution.cpp - main C++ source file (most solutions use C++20, with some in C++17 or C++14)
• occasionally *.h - header-only implementation on C++
• rarely solution.c - ANSI C solution

Problem Domains

The tasks span a wide range of computational and algorithmic topics, including:

• Data Structures: dynamic arrays, queues, trees, hash sets, and balanced BSTs
• Graph Algorithms: maximum flow, topological sorting, reachability, and probabilistic graph properties
• Dynamic Programming & Greedy Methods: optimization under constraints, combinatorial counts, and state-based decisions
• String Algorithms: prefix and Z-functions, suffix structures, pattern matching (exact and fuzzy), automata equivalence, and substring statistics
• Mathematical & Geometric Problems: proportions, distances, and combinatorial geometry
• Search and Optimization: binary search, sliding window optimization, and range queries
• Text & Data Processing: ranking, filtering, and parsing of large datasets efficiently
• Advanced Topics: Burrows–Wheeler transform, Aho–Corasick automaton with wildcards, and suffix automata for substring analysis

Difficulty Overview

Category	Description
Easy	Introductory problems covering fundamental algorithms and data structures. Focus on stacks, queues, prefix/suffix processing, and simple greedy or two-pointer techniques. Typical examples include bracket validation, sliding windows, sequence merging, and basic optimization tasks.
Moderate	Intermediate algorithmic challenges involving string processing, graph traversal, and moderate dynamic programming. Includes tasks on prefix/Z-functions, automaton equivalence, knapsack variations, flow problems, and frequency analysis.
Challenging	Advanced problems requiring efficient data structures and multi-step reasoning. Emphasizes range queries, order statistics, graph-based modeling, and multidimensional updates. Tasks often combine algorithms such as binary search, network flow, and tree-based structures.
Hard	Expert-level and research-oriented algorithms. Centers on advanced string theory, compression, and pattern matching - including suffix automata, Burrows–Wheeler transform, fuzzy matching, and shortest superstring problems. These require precise implementation and strong asymptotic optimization.

Conceptual Focus

This repository is designed to:

• Provide practical algorithm implementations across varied domains
• Demonstrate problem-solving approaches
• Serve as a reference for competitive programming and interview preparation
• Offer scalable and optimized code patterns for high-performance problem solving

Conventions

• Language: most solutions are implemented in C++
• Complexity Notes: each problem README specifies time and memory constraints

Getting Started

1. Navigate to a difficulty folder of your choice
2. Select a task subfolder
3. Read its individual README.md for a detailed explanation
4. Review (and compile) the solution file to explore the algorithm