DEV Community: YASH SAWARKAR

🧙‍♂️ JavaScript Decorators Explained – Like Magic, but Real!

YASH SAWARKAR — Sun, 04 May 2025 16:49:41 +0000

Decorators are a powerful way to enhance classes and their members (methods or properties) without touching their original code directly. 🎯
They let you decorate behaviour in a clean and reusable way. Like adding toppings to a pizza 🍕

⚠️ Decorators are a Stage-3 proposal in JavaScript. You can use them with TypeScript or Babel.

🔍 What is a Decorator?

A decorator is a special function you can attach to:

A class
A class method
A class property

It looks like this:

@myDecorator
class MyClass {}

Or for methods:

class MyClass {
  @log
  doSomething() {}
}

⚙️ How Do Decorators Work Behind the Scenes?

Think of a decorator as a function that wraps the original function, property, or class to change its behavior.

Here's what happens behind the scenes for method decorators:

When the class is defined, decorators are executed.
The decorator function receives three arguments:

target: The class prototype (for instance methods) or constructor (for static methods)
propertyKey: The name of the method/property being decorated
descriptor: The property descriptor that describes the method
1. The decorator can change the method (e.g., add logging) by modifying the descriptor.

Behind-the-scenes sketch:

function log(target, propertyKey, descriptor) {
  // Modify the original function
  const originalMethod = descriptor.value;
  descriptor.value = function (...args) {
    console.log(`Calling ${propertyKey} with`, args);
    return originalMethod.apply(this, args);
  };
  return descriptor;
}

Decorators don’t execute at runtime like normal code — they execute when the class is first defined.

🧪 Basic Example – Logging Function Calls

Let’s see a working example:

function log(target, propertyName, descriptor) {
  const original = descriptor.value;

  descriptor.value = function (...args) {
    console.log(`📞 ${propertyName} called with`, args);
    const result = original.apply(this, args);
    console.log(`✅ ${propertyName} returned`, result);
    return result;
  };

  return descriptor;
}

class Calculator {
  @log
  add(a, b) {
    return a + b;
  }
}

const calc = new Calculator();
calc.add(5, 3);

🧰 Real-World Use Cases

1. ✅ Logging and Debugging

Great for tracing code behavior during development.

2. 🔐 Authorization Guards

function requireAdmin(target, key, descriptor) {
  const original = descriptor.value;
  descriptor.value = function (...args) {
    if (!this.isAdmin) {
      throw new Error("⛔️ Access denied");
    }
    return original.apply(this, args);
  };
  return descriptor;
}

class Dashboard {
  constructor(isAdmin) {
    this.isAdmin = isAdmin;
  }

  @requireAdmin
  deleteUser() {
    console.log("🗑️ User deleted");
  }
}

const admin = new Dashboard(true);
admin.deleteUser(); // 🗑️ User deleted

const guest = new Dashboard(false);
guest.deleteUser(); // ⛔️ Error: Access denied

3. 🧹 Auto-Binding Methods

function autobind(target, key, descriptor) {
  const original = descriptor.value;
  return {
    configurable: true,
    enumerable: false,
    get() {
      return original.bind(this);
    },
  };
}

class Printer {
  message = "💨 Hello from Printer!";

  @autobind
  print() {
    console.log(this.message);
  }
}

const p = new Printer();
const printFn = p.print;
printFn(); // 💨 Hello from Printer!

🔬 Types of Decorators

JavaScript (and especially TypeScript) supports different types of decorators:

Type	Target	Purpose
Class decorator	Whole class	Modify or enhance a class
Method decorator	Class method	Wrap or replace a method
Property decorator	Class property	Add metadata or transformations
Parameter decorator	Method param	Metadata for method parameters

📊 Setup for TypeScript

Enable decorators in your tsconfig.json:

{
  "compilerOptions": {
    "target": "ES6",
    "experimentalDecorators": true
  }
}

For Babel, use: @babel/plugin-proposal-decorators

🧠 Summary Table

Feature	Target	Purpose
`@log`	Method	Logging/debugging
`@autobind`	Method	Fix `this` binding
`@requireAdmin`	Method	Authorization check

💭 Deeper Insight: Why Decorators?

Decorators provide a declarative way to apply cross-cutting concerns like:

✅ Logging
🔁 Memoization
🔐 Access control
💾 Caching
⌚ Rate limiting

Rather than adding repetitive boilerplate in every method, you write it once in a decorator and reuse it across your codebase.

This makes your business logic clean, reusable, and easy to read 💡

💬 Final Thoughts

Decorators help keep your code clean, elegant, and modular.
They're like invisible helpers that wrap around your logic — magical, but under your control 💫

Use them wisely and your code will thank you!

📖 Resources

Happy Decorating! 🌟

Mastering Recursion: Think Like a Recursive Ninja! 🥷

YASH SAWARKAR — Sun, 09 Mar 2025 07:43:00 +0000

Recursion is like magic! 🪄 You solve a big problem by breaking it down into smaller versions of itself. But how do you know if recursion is the right approach? 🤔

How to Identify a Recursive Problem? 🔍

Recursion is applicable when a problem can be broken down into smaller subproblems that resemble the original one. Here are key aspects to check:

1. Self-Replication: If a function can be defined in terms of itself, recursion is a strong candidate! 🚀

Example: Fibonacci Sequence 🌀

 int fibonacci(int n) {
   if (n == 0 || n == 1) return n; // Base case
   return fibonacci(n - 1) + fibonacci(n - 2); // Recursive relation
 }

The Fibonacci function is self-replicating because it calculates
fib(n) by solving fib(n-1) and fib(n-2).

2. Base Case Matters: Can solving a small version of the problem help solve the bigger one? ✅

In Fibonacci, the base case is fib(0) = 0 and fib(1) = 1. These smallest cases form the foundation for solving larger values.

3. Choices, Choices Everywhere!: If you're making decisions at each step (like including/excluding elements), recursion might be the way. 🔄

For example, when finding all subsequences of a string like "abc", we have two choices at each step:

Include the current character.
Exclude the current character.

This naturally forms a recursive structure! 🎭

void findSubsequences(String s, int index, String current) {
  if (index == s.length()) {
    System.out.println(current); // Base case: Print the current subsequence
    return;
  }

  // Include the character
  findSubsequences(s, index + 1, current + s.charAt(index));

  // Exclude the character
  findSubsequences(s, index + 1, current);
}

💡 Thinking Recursively:

The base case is when index == s.length(), meaning we've formed a valid subsequence.
The recursion ensures that every possible combination is explored!

This choice-based recursion is widely used in problems like subsets, combinations, and decision trees. 🌳

Example: Include-Exclude Recursive Tree 🌳

Let's visualize how recursion works for generating all subsequences of "abc":

                ""   (Start)
               /   \
            "a"    ""  (Include 'a' / Exclude 'a')
           /   \    /   \
       "ab"  "a"  "b"   "" (Include/Exclude 'b')
       /  \   / \   / \   / \
    "abc" "ab" "ac" "a" "bc" "b" "c" "" (Final Subsequences)

Each step involves a choice:
1️⃣ Include the character → Move down the left branch.
2️⃣ Exclude the character → Move down the right branch.

This decision tree explores all possible subsequences, and the base case is when we've processed all characters (index == s.length()). ✅

The Key Concept of Recursion 🧩

At its core, recursion has three fundamental parts:

Base Case: The smallest valid input for which the answer is known directly.
Recursive Relation: A way to relate the smallest valid case to the current case.
Induction: The process of using the recursive relation to produce the desired output.

💡 Example: Fibonacci Explained Using These Concepts:

Base Case: fib(0) = 0, fib(1) = 1.
Recursive Relation: fib(n) = fib(n-1) + fib(n-2).
Induction: Using known smaller values, we build up the final result.

If you can define these three, you're on the right track to solving a problem recursively! 🚀

Common Recursive Patterns 🔄

1️⃣ Include-Exclude Pattern 🎭

This is a classic pattern where you make binary choices: Include an element or Exclude it. This is super common in subset problems!

Example: Finding All Subsequences of a String 📜

void findSubsequences(String s, int index, String current) {
  if (index == s.length()) {
    System.out.println(current); // Base case: Print the current subsequence
    return;
  }

  // Include the character
  findSubsequences(s, index + 1, current + s.charAt(index));

  // Exclude the character
  findSubsequences(s, index + 1, current);
}

💡 Example Input: "abc"

💡 Example Output:

abc
ab
ac
a
bc
b
c

💡 Thinking Recursively:

At each step, we either take the character or leave it.
Base case? When index == s.length(), we have formed a valid subsequence!

2️⃣ Explore All Possible Ways 🌍

Sometimes, recursion is just brute-force exploration of all possible paths! 🏃‍♂️

Example: Maze Problem 🏰

boolean canReachEnd(int[][] maze, int x, int y) {
  if (x < 0 || y < 0 || x >= maze.length || y >= maze[0].length || maze[x][y] == 1) return false; // Base case
  if (x == maze.length - 1 && y == maze[0].length - 1) return true; // Reached end!

  return canReachEnd(maze, x + 1, y) || canReachEnd(maze, x, y + 1); // Explore all paths
}

💡 Thinking Recursively:

If we can move down or right and reach the destination, we win! 🎉
Base case? If out of bounds or on an obstacle, return false.

3️⃣ Choices & Decision Tree 🌳

When solving problems like permutations or word break, you have multiple choices at every step. This forms a decision tree!

Example: Generating Parentheses 👶

void generate(int open, int close, String current, List<String> result) {
  if (open == 0 && close == 0) {
    result.add(current);
    return;
  }

  if (open > 0) generate(open - 1, close, current + "(", result);
  if (close > open) generate(open, close - 1, current + ")", result);
}

💡 Thinking Recursively:

Two choices: Add ( if available or ) if valid.
Base case? When no brackets are left.

4️⃣ IBH (Induction, Base Case, Hypothesis) 🧠

This is a framework for proving recursion is correct! ✨

Base Case: The smallest valid input is handled directly.
Recursive Relation: A relation is established between the smallest valid case and the current case.
Induction: The process of using this relation to generate the final output.

Example: Tower of Hanoi 🗼

void hanoi(int n, char from, char to, char aux) {
  if (n == 1) {
    System.out.println("Move disk 1 from " + from + " to " + to);
    return;
  }
  hanoi(n - 1, from, aux, to);
  System.out.println("Move disk " + n + " from " + from + " to " + to);
  hanoi(n - 1, aux, to, from);
}

💡 Thinking Recursively:

Base case? Moving one disk is trivial.
Hypothesis? Assume n-1 works.
Induction? Use n-1 to move n!

Final Thoughts 🏁

Recursion is an art! 🎨 If you spot self-replication, decisions, or ways to break a problem down, think recursively! 🔄

👉 Which recursion pattern do you struggle with the most? Let me know! 🚀

Dijkstra's Shortest Path Algorithm Implementation

YASH SAWARKAR — Sun, 18 Aug 2024 10:25:30 +0000

Dijkstra's algorithm is used to find the shortest paths from a source node to all other nodes in a directed or undirected weighted graph. Dijkstra's algorithm is a well-known algorithm for finding the shortest paths between nodes in a graph, particularly useful when dealing with graphs without negative edge weights.

Key Concepts

Dijkstra's Algorithm

Purpose: To find the shortest path from a single source node to all other nodes in a graph.
Limitations:
- Not applicable to graphs with negative edge weights.
- Cannot handle graphs containing negative cycles.
- Does not provide information about unreachable nodes.

Graph Representation

The graph is represented using an adjacency list, where each node is mapped to a list of its neighbors and the respective edge weights.

Code Breakdown

1. Class Definition: `DirectedWeightedGraph`

Adjacency List: The graph is stored as an unordered_map where each node has a list of its neighboring nodes and the weights of the edges connecting them.
Functions:
- insertEdge: Adds an edge to the graph. It supports both directed and undirected graphs.
- printAdjacencyList: Prints the adjacency list of the graph for debugging purposes.
- dijkstrasShortestPath: Implements Dijkstra's algorithm to find the shortest path from a source node to all other nodes.

2. Function: `insertEdge`

Parameters:
- source: The starting node of the edge.
- destination: The ending node of the edge.
- weight: The weight of the edge.
- isDirected: Boolean indicating whether the graph is directed or undirected.
Functionality:
- If the graph is directed, an edge is added from the source to the destination.
- If the graph is undirected, edges are added in both directions.

3. Function: `dijkstrasShortestPath`

Parameters:
- source: The source node from which shortest paths are calculated.
- numberOfNodes: Total number of nodes in the graph.
Data Structures:
- shortestDistances: A vector storing the shortest distance from the source to each node, initialized to INT_MAX to signify infinity.
- nodesSet: A set that acts as a priority queue, storing pairs of node distances and node values, sorted by distance.
Algorithm:
- The source node is inserted into the set with a distance of 0.
- The algorithm iterates over the set, picking the node with the smallest distance (similar to BFS).
- For each node, it checks its neighbors and updates their shortest distances if a shorter path is found through the current node.
- The updated neighbors are reinserted into the set for further processing.

4. Main Function

Graph Construction: The graph is built by inserting edges with specified weights.
Shortest Path Calculation: Dijkstra's algorithm is run from a specified source node.
Output: The shortest distances from the source node to all other nodes are printed.

Example


#include <climits>
#include <iostream>
#include <list>
#include <ostream>
#include <set>
#include <unordered_map>
#include <utility>
#include <vector>

using namespace std;

// NOTE:
// -> this approach can be used on both directed and undirected graphs
// Limitations of Dijkstra's Algorithm:
//  - Inapplicable to graphs with negative edge weights.
//  - Unable to handle graphs containing negative cycles.
//  - Does not provide information about unreachable nodes.

// Class representing a directed weighted graph
class DirectedWeightedGraph {
public:
  // Adjacency List representation: <vertex value, <neighbor, weight>>
  unordered_map<int, list<pair<int, int>>> adjacencyList;

  // Function to insert an edge into the graph
  void insertEdge(int source, int destination, int weight, bool isDirected) {
    if (isDirected) {
      // For directed graph, only one entry is added for the source to
      // destination
      adjacencyList[source].push_back({destination, weight});
    } else {
      // For undirected graph, entries are added for both source to destination
      // and destination to source
      adjacencyList[source].push_back({destination, weight});
      adjacencyList[destination].push_back({source, weight});
    }
  }

  // Function to print the adjacency list
  void printAdjacencyList() {
    for (auto vertex : adjacencyList) {
      cout << vertex.first << " : ";
      for (auto neighbor : vertex.second) {
        cout << " { " << neighbor.first << " , " << neighbor.second << " } ";
      }
      cout << endl;
    }
  }

  // NOTE: unlike directed graphs here we can't use topological sort to get the
  // element in a dependency order
  // -> so we use min min-heap or set to get the node with the min distance .
  // -> isentially it's bfs only but here we are using set instead of queue .

  // Function to find the shortest paths using Dijkstra's algorithm
  vector<int> dijkstrasShortestPath(int source, int numberOfNodes) {

    // Vector to store the shortest distances from the source to each node
    // NOTE: using unordered_map could be a better / vercitle chaoice
    // -> as we won't need to handle the indexes manually then
    vector<int> shortestDistances(numberOfNodes + 1, INT_MAX);

    // Set to keep track of nodes and their distances, sorted by distance
    // NOTE: using min-heap could be a better chaoice here
    //  -> but then we'll have to write a custom comparator for it .
    set<pair<int, int>> nodesSet;

    // insert a source node into set and mark it's distance as 0
    nodesSet.insert({0, source});
    shortestDistances[source] = 0;

    // Dijkstra's algorithm
    while (!nodesSet.empty()) {

      // Get the node with the smallest distance
      auto currentNode = nodesSet.begin();

      // as a .begin() returns an itirator we need to dereference it with *
      auto currentPair = *(currentNode);

      // get the current node value and it's shortest distance so far
      int currentNodeValue = currentPair.second;
      int currentNodeDistance = currentPair.first;

      // Remove the current node from the set
      nodesSet.erase(nodesSet.begin());

      // Iterate over neighbors of the current node
      for (auto neighborPair : adjacencyList[currentNodeValue]) {

        // take the neighborDistance and neighborNodeValue out of neighborPair
        int neighborNodeValue = neighborPair.first;
        int neighborDistance = neighborPair.second;

        // Update the distance if the currentNodeDistance in addition to the
        // distance to the neighbor from the current node is smaller to the
        // distance of the neighbor.
        if (currentNodeDistance + neighborDistance <
            shortestDistances[neighborNodeValue]) {

          // Remove the previous entry for the neighbor from the set
          auto previousEntry = nodesSet.find(
              {shortestDistances[neighborNodeValue], neighborNodeValue});

          // if the previous entry of a neighbor pair is found erase it
          if (previousEntry != nodesSet.end()) {
            nodesSet.erase(previousEntry);
          }

          // Update the shortest distance for the neighbor node
          shortestDistances[neighborNodeValue] =
              currentNodeDistance + neighborDistance;

          // insert the updated entry back into the set for further processing
          // NOTE: we are inserting this updated neighbor into the set to
          // process it's neighbors and recalculate their distances accordingly.
          nodesSet.insert(
              {shortestDistances[neighborNodeValue], neighborNodeValue});
        }
      }
    }
    return shortestDistances;
  }
};

int main() {

  // Create a directed weighted graph object
  DirectedWeightedGraph weightedGraph;

  // Add edges to the graph
  weightedGraph.insertEdge(1, 6, 14, false);
  weightedGraph.insertEdge(1, 3, 9, false);
  weightedGraph.insertEdge(1, 2, 7, false);
  weightedGraph.insertEdge(2, 3, 10, false);
  weightedGraph.insertEdge(2, 4, 15, false);
  weightedGraph.insertEdge(3, 4, 11, false);
  weightedGraph.insertEdge(6, 3, 2, false);
  weightedGraph.insertEdge(6, 5, 9, false);
  weightedGraph.insertEdge(5, 4, 6, false);

  // Specify the source node and the total number of nodes in the graph
  int sourceNode = 6;
  int totalNodes = 6;

  // Find the shortest paths from the source to all nodes
  vector<int> shortestPaths =
      weightedGraph.dijkstrasShortestPath(sourceNode, totalNodes);

  // Print the adjacency list of the graph
  // weightedGraph.printAdjacencyList();

  // Display the shortest paths from the source to each node
  cout << "Shortest path from " << sourceNode << " to each node is : " << endl;

  // Print the shortest path lengths
  for (int i = 0; i < shortestPaths.size(); i++) {
    cout << i << " -> " << shortestPaths[i] << endl;
  }
  cout << endl;
}

This output indicates the shortest distance from node 6 to all other nodes. Note that 2147483647 (equivalent to INT_MAX) indicates that a node is unreachable from the source.

Key Notes:

Set vs Min-Heap: While the code uses a set to get the minimum distance node, a min-heap (priority queue) could be more efficient, albeit with additional complexity.
Handling Large Graphs: The algorithm works well for graphs without negative weights but may need adjustments for larger or more complex graphs, such as using a priority queue.

Time Complexity:

Dijkstra's Algorithm: O((V + E) log V) where V is the number of vertices and E is the number of edges.

Space Complexity:

Dijkstra's Algorithm: O(V + E) for storing the graph, distances, and the set.

Cycle Detection in a Directed Graph

YASH SAWARKAR — Sun, 18 Aug 2024 10:18:18 +0000

Detect cycles in a directed graph using two different approaches:

DFS Approach: We track the nodes visited in the current recursive path using an additional data structure.
BFS Approach (Kahn's Algorithm): We check for cycles using the topological sort method. If the graph cannot be fully topologically sorted, a cycle exists.

Approach

1. DFS Cycle Detection

Visited and DFS Visited: We use two data structures to track:
- visited: If a node has been visited at least once during any DFS traversal.
- dfsVisited: If a node is currently in the recursive call stack.
Cycle Detection: A cycle exists if we encounter a node in the current path (dfsVisited) during traversal.

2. BFS Cycle Detection (Kahn's Algorithm)

Topological Sorting: A topological sort of a graph should include all nodes. If it doesn't, then some nodes couldn't be processed due to a cycle, indicating the presence of a cycle.
Indegree Calculation: We calculate the indegree of each node and start BFS traversal from nodes with indegree 0. During traversal, we reduce the indegree of each neighbor.

Code Explanation

#include <iostream>
#include <queue>
#include <unordered_map>
#include <vector>
#include <list>

using namespace std;

// Function to check for a cycle using DFS
bool checkCycleDfs(int node, unordered_map<int, bool> &visited,
                   unordered_map<int, bool> &dfsVisited,
                   unordered_map<int, list<int>> &adj) {
  visited[node] = true;
  dfsVisited[node] = true;

  for (auto neighbor : adj[node]) {
    if (!visited[neighbor]) {
      if (checkCycleDfs(neighbor, visited, dfsVisited, adj)) {
        return true;
      }
    } else if (dfsVisited[neighbor]) {
      return true; // Cycle found: neighbor is already in the current DFS path
    }
  }

  dfsVisited[node] = false; // Backtrack to explore other paths
  return false;
}

// Function to do Topological sort using BFS traversal
vector<int> topoLogicalSort_BFS(unordered_map<int, list<int>> &adjList,
                                int numberOfNodes) {
  queue<int> bfsQue;
  unordered_map<int, int> indegree;
  vector<int> ans;

  // Count indegrees of each node
  for (int i = 0; i < numberOfNodes; i++) {
    for (auto it : adjList[i]) {
      indegree[it]++;
    }
  }

  // Add nodes with 0 indegrees as starting points
  for (int i = 0; i < numberOfNodes; i++) {
    if (indegree[i] == 0) {
      bfsQue.push(i);
    }
  }

  // Perform BFS traversal
  while (!bfsQue.empty()) {
    int node = bfsQue.front();
    bfsQue.pop();
    ans.push_back(node);

    for (auto nbr : adjList[node]) {
      indegree[nbr]--;
      if (indegree[nbr] == 0) {
        bfsQue.push(nbr);
      }
    }
  }
  return ans;
}

// Function to detect a cycle in a graph using both DFS and BFS
vector<bool> detectCycleInGraph(int n, vector<pair<int, int>> &edges) {
  unordered_map<int, list<int>> adj;
  unordered_map<int, bool> visited;
  unordered_map<int, bool> dfsVisited;

  bool ans_DFS = false;
  bool ans_BFS = false;

  // Create adjacency list
  for (int i = 0; i < edges.size(); i++) {
    int u = edges[i].first;
    int v = edges[i].second;
    adj[u].push_back(v);
  }

  // DFS cycle detection
  for (int i = 1; i <= n; i++) {
    if (!visited[i]) {
      if (checkCycleDfs(i, visited, dfsVisited, adj)) {
        ans_DFS = true;
        break;
      }
    }
  }

  // BFS cycle detection
  vector<int> topoSort = topoLogicalSort_BFS(adj, n);
  if (topoSort.size() < n) {
    ans_BFS = true;
  }

  return {ans_BFS, ans_DFS};
}

int main() {
  int n = 4;
  vector<pair<int, int>> edges = {{1, 2}, {2, 3}, {3, 1}}; // Has a cycle

  vector<bool> hasCycle = detectCycleInGraph(n, edges);

  cout << "hasCycle (BFS) : " << hasCycle[0] << endl;
  cout << "hasCycle (DFS) : " << hasCycle[1] << endl;

  return 0;
}

Key Points:

DFS: Detects cycles by checking if a node is revisited in the current path.
BFS: Detects cycles by attempting topological sorting. If topological sorting is incomplete, a cycle exists.

Time Complexity:

DFS: O(V + E), where V is the number of vertices and E is the number of edges.
BFS (Kahn's Algorithm): O(V + E).

Space Complexity:

DFS: O(V) for the visited and dfsVisited arrays.
BFS: O(V) for the indegree array and BFS queue.

Topological Sorting to Determine Course Order

YASH SAWARKAR — Sun, 18 Aug 2024 10:07:26 +0000

The problem is to determine the order in which courses should be taken given their prerequisites. This can be represented as a Directed Acyclic Graph (DAG), where courses are nodes, and edges represent the prerequisites.

Approach

The approach used here is Topological Sorting using BFS (Kahn’s Algorithm). The idea is to check if the courses can be arranged in a sequence such that for every directed edge U -> V, course U comes before course V.

Key Steps:

Create an Adjacency List:
- The adjacency list represents the graph where each node (course) points to its dependent nodes (courses that depend on it as a prerequisite).
Calculate In-Degrees:
- In-degree of a node is the number of edges pointing to it. Courses with zero in-degrees can be taken without any prerequisites.
BFS Traversal:
- Start from the nodes with zero in-degrees, and reduce the in-degrees of their neighboring nodes. If a node's in-degree becomes zero, it means all its prerequisites have been met, and it can be added to the course order.
Check for Completion:
- If all courses are included in the topological order, a valid order exists. Otherwise, it's impossible to complete all courses.

Code Explanation

#include <iostream>
#include <list>
#include <queue>
#include <unordered_map>
#include <vector>

using namespace std;

class Solution {
public:
  // Function to perform Topological sort using BFS traversal
  vector<int> topoLogicalSort_BFS(int numNodes, unordered_map<int, list<int>> &adjacencyList) {
    queue<int> bfsQueue; // Queue for BFS traversal
    unordered_map<int, int> inDegree; // Map to store in-degrees of nodes
    vector<int> result; // Result vector to store topological order

    // Count in-degrees of each node
    for (int i = 0; i < numNodes; i++) {
      for (auto neighbor : adjacencyList[i]) {
        inDegree[neighbor]++;
      }
    }

    // Add nodes with 0 in-degrees as starting points
    for (int i = 0; i < numNodes; i++) {
      if (inDegree[i] == 0) {
        bfsQueue.push(i);
      }
    }

    // Perform BFS traversal
    while (!bfsQueue.empty()) {
      int currentNode = bfsQueue.front(); // Extract the front node for processing
      bfsQueue.pop();
      result.push_back(currentNode); // Add the node to the result

      // Visit neighbors, decrease their in-degrees, and enqueue if in-degree becomes 0
      for (auto neighbor : adjacencyList[currentNode]) {
        inDegree[neighbor]--;
        if (inDegree[neighbor] == 0) {
          bfsQueue.push(neighbor);
        }
      }
    }

    return result; // Return the topological order
  }

  // Function to return the order of courses according to their dependencies
  vector<int> findOrder(int numCourses, vector<vector<int>> &prerequisites) {
    unordered_map<int, list<int>> adjacencyList;

    // Build the adjacency list
    for (auto prerequisite : prerequisites) {
      int course = prerequisite[0];
      int prerequisiteForCourse = prerequisite[1];
      adjacencyList[prerequisiteForCourse].push_back(course);
    }

    // Get the topological order of courses
    vector<int> topologicalOrder = topoLogicalSort_BFS(numCourses, adjacencyList);

    // Return the topologicalOrder if all courses can be arranged, else return an empty vector
    return (topologicalOrder.size() == numCourses) ? topologicalOrder : vector<int>();
  }
};

int main() {
  Solution solution;

  int numCourses = 4;
  vector<vector<int>> prerequisites = {{1, 0}, {2, 0}, {3, 1}, {3, 2}};

  vector<int> courseOrder = solution.findOrder(numCourses, prerequisites);

  // Display the result
  if (!courseOrder.empty()) {
    cout << "Course order: ";
    for (int course : courseOrder) {
      cout << course << " ";
    }
    cout << endl;
  } else {
    cout << "No valid course order exists." << endl;
  }

  return 0;
}

Time Complexity
O(V + E), where V is the number of vertices (courses) and E is the number of edges (prerequisites). Each node and each edge is processed exactly once.

Space Complexity
O(V + E) for storing the adjacency list and in-degree array.

Interleaving Two Strings

YASH SAWARKAR — Sun, 18 Aug 2024 09:51:09 +0000

The problem is to determine whether a given string s3 can be formed by interleaving two other strings s1 and s2. The interleaving of the two strings must preserve the order of characters in both strings.

Recursive Approach
The first method used is the recursive approach. This approach tries to match each character of s3 with either s1 or s2. If a match is found, the function recursively checks the remaining characters.

bool solveUsingRecursion(string &s1, string &s2, string &s3, int i, int j, int k) {
  if (i >= s1.length() && j >= s2.length() && k >= s3.length()) {
    return true;
  }

  bool flag = false;

  // Check if the current character of s1 matches s3
  if (i < s1.length() && s1[i] == s3[k]) {
    flag = flag || solveUsingRecursion(s1, s2, s3, i + 1, j, k + 1);
  }

  // Check if the current character of s2 matches s3
  if (j < s2.length() && s2[j] == s3[k]) {
    flag = flag || solveUsingRecursion(s1, s2, s3, i, j + 1, k + 1);
  }

  return flag;
}

In this code:
The base case checks if all characters have been matched. If so, it returns true.
The function tries to match s3[k] with s1[i] or s2[j]. If a match is found, the function recursively checks the rest.
Time Complexity: The time complexity of this approach is exponential,
(O(2^{n+m})), due to the branching factor of checking two possibilities at each step.

Memoization Approach
To optimize the recursive approach, we can use memoization to store the results of subproblems and avoid redundant calculations.

bool solveUsingMemoization(string &s1, string &s2, string &s3, int i, int j, int k, vector<vector<vector<int>>> &dp) {
  if (i >= s1.length() && j >= s2.length() && k >= s3.length()) {
    return true;
  }

  if (dp[i][j][k] != -1) {
    return dp[i][j][k];
  }

  bool flag = false;

  if (i < s1.length() && s1[i] == s3[k]) {
    flag = flag || solveUsingMemoization(s1, s2, s3, i + 1, j, k + 1, dp);
  }

  if (j < s2.length() && s2[j] == s3[k]) {
    flag = flag || solveUsingMemoization(s1, s2, s3, i, j + 1, k + 1, dp);
  }

  return dp[i][j][k] = flag;
}

Here, a 3D dp table stores the results of subproblems, reducing the overall time complexity to O(n×m×p), where n, m, and p are the lengths of s1, s2, and s3, respectively.

Tabulation Approach
The next optimization is using tabulation, where we build the solution iteratively rather than recursively.

bool solveUsingTabulation(string &s1, string &s2, string &s3) {
  int len1 = s1.length(), len2 = s2.length(), len3 = s3.length();
  vector<vector<vector<int>>> dp(len1 + 1, vector<vector<int>>(len2 + 1, vector<int>(len3 + 1, 0)));

  dp[len1][len2][len3] = true;

  for (int i = len1; i >= 0; i--) {
    for (int j = len2; j >= 0; j--) {
      for (int k = len3; k >= 0; k--) {
        if (i >= len1 && j >= len2 && k >= len3) {
          continue;
        }

        bool flag = false;

        if (i < len1 && s1[i] == s3[k]) {
          flag = flag || dp[i + 1][j][k + 1];
        }

        if (j < len2 && s2[j] == s3[k]) {
          flag = flag || dp[i][j + 1][k + 1];
        }

        dp[i][j][k] = flag;
      }
    }
  }

  return dp[0][0][0];
}

This method iteratively fills up a DP table. The time complexity remains the same as memoization, but it is easier to understand and debug.

Space-Optimized Solution
Finally, to reduce space complexity, we use a 1D DP array.

bool isInterleaveOptimized(string a, string b, string c) {
  if (a.length() < b.length()) {
    swap(a, b);
  }

  int n1 = a.length(), n2 = b.length(), n3 = c.length();
  vector<bool> dp(n2 + 1, false);

  if (n1 + n2 != n3) {
    return false;
  }

  for (int i = 0; i <= n1; i++) {
    for (int j = 0; j <= n2; j++) {
      if (i == 0 && j == 0) {
        dp[j] = true;
      } else if (i == 0) {
        dp[j] = dp[j - 1] && (b[j - 1] == c[j - 1]);
      } else if (j == 0) {
        dp[j] = dp[j] && (a[i - 1] == c[i - 1]);
      } else {
        dp[j] = (dp[j] && a[i - 1] == c[i + j - 1]) || (dp[j - 1] && b[j - 1] == c[i + j - 1]);
      }
    }
  }

  return dp[n2];
}

By reducing the problem to a single 1D DP array, we save space while still achieving the desired result.
The space complexity is reduced to O(min(n,m))

Conclusion
This problem can be solved using various methods, each with its trade-offs between time and space complexity. Starting with a recursive approach helps build an understanding, which can be optimized step-by-step to improve efficiency. The final solution is a space-optimized dynamic programming approach, which efficiently checks if s3 is an interleaving of s1 and s2.

House Robber Problem

YASH SAWARKAR — Sun, 18 Aug 2024 09:34:22 +0000

Given a list of houses, each containing some money, you need to determine the maximum amount of money you can rob without robbing two consecutive houses.

For example, if the houses have the following money: [2, 7, 9, 3, 1], the maximum money you can rob is 12 by robbing the first, third, and fifth houses.

Approach to the Solution
To solve this problem, we can break down the solution into a series of increasingly optimized approaches:

Recursive Solution
Memoization Solution
Tabulation Solution
Space-Optimized Tabulation Solution

1. Recursive Solution
The recursive approach is the most straightforward but inefficient. The idea is to try robbing each house and recursively check for the best outcome. For each house, you have two options: rob it or skip it.

If you rob the current house, you cannot rob the next one, so you move to the house after the next.
If you skip the current house, you move to the next house.
The recursive function explores all possible combinations and returns the maximum possible profit.

int solveUsingRecursion(const vector<int> &houses, int currentIndex) {
  if (currentIndex >= houses.size()) {
    return 0;
  }

  int robCurrent = houses[currentIndex] + solveUsingRecursion(houses, currentIndex + 2);
  int skipCurrent = solveUsingRecursion(houses, currentIndex + 1);

  return max(robCurrent, skipCurrent);
}

Time Complexity: (O(2^n)) — Exponential time because it explores all possible combinations.

Space Complexity: (O(n)) — The space complexity is due to the recursion stack.

2. Memoization Solution
The recursive solution has overlapping subproblems, meaning it solves the same subproblem multiple times. We can optimize this using memoization, where we store the results of subproblems in a dp array and reuse them when needed.

int solveUsingMemoization(const vector<int> &houses, int currentIndex, vector<int> &dp) {
  if (currentIndex >= houses.size()) {
    return 0;
  }

  if (dp[currentIndex] != -1) {
    return dp[currentIndex];
  }

  int robCurrent = houses[currentIndex] + solveUsingMemoization(houses, currentIndex + 2, dp);
  int skipCurrent = solveUsingMemoization(houses, currentIndex + 1, dp);

  dp[currentIndex] = max(robCurrent, skipCurrent);
  return dp[currentIndex];
}

Time Complexity: O(n) — Each subproblem is solved only once.

Space Complexity: O(n) — Space is needed for both the dp array and the recursion stack.

3. Tabulation Solution
The tabulation approach eliminates recursion by building the solution iteratively from the base case. We maintain a dp array where each entry represents the maximum money that can be robbed up to that house.

int solveUsingTabulation(const vector<int> &houses) {
  if (houses.empty()) {
    return 0;
  }

  vector<int> maxRobbableAmounts(houses.size(), -1);
  maxRobbableAmounts[houses.size() - 1] = houses.back();

  for (int i = houses.size() - 2; i >= 0; i--) {
    int robCurrent = houses[i] + (i + 2 < houses.size() ? maxRobbableAmounts[i + 2] : 0);
    int skipCurrent = maxRobbableAmounts[i + 1];
    maxRobbableAmounts[i] = max(robCurrent, skipCurrent);
  }

  return maxRobbableAmounts[0];
}

Time Complexity: O(n) — Iterates through the houses list once.

Space Complexity: O(n) — Space is required for the dp array.

4. Space-Optimized Tabulation Solution
The tabulation approach can be further optimized by realizing that the result at each house only depends on the results from the next two houses. Therefore, instead of maintaining a full dp array, we only need three variables to track the necessary results.

int solveUsingSpaceOptimizedTabulation(const vector<int> &houses) {
  if (houses.empty()) {
    return 0;
  }

  int previousAmount = houses.back();
  int nextAmount = 0;
  int currentAmount = 0;

  for (int i = houses.size() - 2; i >= 0; i--) {
    int robCurrent = houses[i] + nextAmount;
    int skipCurrent = previousAmount;

    currentAmount = max(robCurrent, skipCurrent);

    nextAmount = previousAmount;
    previousAmount = currentAmount;
  }

  return previousAmount;
}

Time Complexity: O(n) — Same as tabulation.

Space Complexity: O(1) — Constant space is used for three variables.

Conclusion
The House Robber problem is an excellent example of how dynamic programming can be used to optimize recursive solutions. We started with a simple recursive approach and progressively optimized it by using memoization, tabulation, and finally, a space-optimized solution. Each step reduced the time and space complexity, making the solution more efficient.

Solving the 0 1 Knapsack Problem: From Recursion to Dynamic Programming

YASH SAWARKAR — Sun, 18 Aug 2024 07:19:54 +0000

Given a list of items, each with a weight and a value, determine the maximum value you can achieve without exceeding a given weight capacity (maxWeight). You can only include each item once, and you must decide whether to include or exclude each item.

Example
Let's take an example where you have the following items:

Weights: [1, 2, 4, 5]
Values: [5, 4, 8, 6]
Maximum Weight Capacity: 5

The goal is to maximize the total value of items in the knapsack without exceeding the weight capacity of 5.

Approach 1: Recursive (Brute Force) Solution
The first approach uses recursion to explore all possible combinations of including or excluding each item. The basic idea is to try both options for every item and take the maximum value from these choices.

int knapsackRecursive(vector<int> &weights, vector<int> &values, int n, int maxWeight, int currentIndex) {
  if (currentIndex >= n) {
    return 0;
  }

  int include = 0;
  if (maxWeight - weights[currentIndex] >= 0) {
    include = values[currentIndex] + knapsackRecursive(weights, values, n, maxWeight - weights[currentIndex], currentIndex + 1);
  }

  int exclude = knapsackRecursive(weights, values, n, maxWeight, currentIndex + 1);

  return max(include, exclude);
}

Time Complexity:

O(2^n) because each item can either be included or excluded, leading to an exponential number of combinations.

Space Complexity:

O(n) due to the depth of the recursion stack.

Approach 2: Memoization
To optimize the recursive approach, we can use memoization. This technique stores the results of subproblems, avoiding redundant calculations.

int knapsackMemoization(vector<int> &weights, vector<int> &values, int n, int maxWeight, int currentIndex, vector<vector<int>> &memo) {
  if (currentIndex >= n) {
    return 0;
  }

  if (memo[maxWeight][currentIndex] != -1) {
    return memo[maxWeight][currentIndex];
  }

  int include = 0;
  if (maxWeight - weights[currentIndex] >= 0) {
    include = values[currentIndex] + knapsackMemoization(weights, values, n, maxWeight - weights[currentIndex], currentIndex + 1, memo);
  }

  int exclude = knapsackMemoization(weights, values, n, maxWeight, currentIndex + 1, memo);

  memo[maxWeight][currentIndex] = max(include, exclude);
  return memo[maxWeight][currentIndex];
}

Time Complexity:

O(n * maxWeight) because each subproblem is solved only once and stored for future reference.

Space Complexity:

O(n * maxWeight) due to the storage required for the memoization table.

Approach 3: Tabulation (Bottom-Up Dynamic Programming)
The tabulation approach eliminates recursion by iteratively solving subproblems and storing the results in a table. This approach builds the solution from the base cases upward.

int knapsackTabulation(vector<int> &weights, vector<int> &values, int n, int maxWeight) {
  vector<vector<int>> dp(maxWeight + 1, vector<int>(n + 1, -1));

  for (int k = 0; k <= maxWeight; k++) {
    dp[k][n] = 0;
  }

  for (int i = 0; i <= maxWeight; i++) {
    for (int j = n - 1; j >= 0; j--) {
      int include = 0;
      if (i - weights[j] >= 0) {
        include = values[j] + dp[i - weights[j]][j + 1];
      }
      int exclude = dp[i][j + 1];
      dp[i][j] = max(include, exclude);
    }
  }

  return dp[maxWeight][0];
}

Time Complexity:

O(n * maxWeight) because we fill a table of size n * maxWeight.

Space Complexity:

O(n * maxWeight) for the table that stores the results of subproblems.

Approach 4: Optimized Tabulation (2D to 1D)
By observing that each row of the table only depends on the previous row, we can reduce space complexity by using two 1D arrays instead of a 2D table.

int knapsackTabulationOptimized2D1D(vector<int> &weights, vector<int> &values, int n, int maxWeight) {
  vector<int> curr(maxWeight + 1, -1);
  vector<int> next(maxWeight + 1, 0);

  for (int j = n - 1; j >= 0; j--) {
    for (int i = 0; i <= maxWeight; i++) {
      int include = 0;
      if (i - weights[j] >= 0) {
        include = values[j] + next[i - weights[j]];
      }
      int exclude = next[i];
      curr[i] = max(include, exclude);
    }
    next = curr;
  }
  return next[maxWeight];
}

Time Complexity:

O(n * maxWeight) similar to the previous approach.

Space Complexity:

O(maxWeight) reduced from O(n * maxWeight) to O(maxWeight).

Approach 5: Further Optimized Tabulation (1D Array)
Finally, we can optimize even further by realizing that we only need one 1D array to store the results, updating it in place.

int knapsackTabulationOptimized1D(vector<int> &weights, vector<int> &values, int n, int maxWeight) {
  vector<int> dp(maxWeight + 1, 0);

  for (int j = n - 1; j >= 0; j--) {
    for (int i = maxWeight; i >= 0; i--) {
      int include = 0;
      if (i - weights[j] >= 0) {
        include = values[j] + dp[i - weights[j]];
      }
      int exclude = dp[i];
      dp[i] = max(include, exclude);
    }
  }
  return dp[maxWeight];
}

Time Complexity:

O(n * maxWeight) as it iterates over all possible subproblems.

Space Complexity:

O(maxWeight) making this the most space-efficient approach.

Conclusion
The Knapsack problem can be solved using various approaches, ranging from brute-force recursion to highly optimized dynamic programming techniques. The choice of method depends on the constraints and requirements of the problem. As we've seen, by analyzing the problem and leveraging dynamic programming, we can significantly reduce both time and space complexities.

DEV Community: YASH SAWARKAR

🧙‍♂️ JavaScript Decorators Explained – Like Magic, but Real!

🔍 What is a Decorator?

⚙️ How Do Decorators Work Behind the Scenes?

🧪 Basic Example – Logging Function Calls

🧰 Real-World Use Cases

1. ✅ Logging and Debugging

2. 🔐 Authorization Guards

3. 🧹 Auto-Binding Methods

🔬 Types of Decorators

📊 Setup for TypeScript

🧠 Summary Table

💭 Deeper Insight: Why Decorators?

💬 Final Thoughts

📖 Resources

Mastering Recursion: Think Like a Recursive Ninja! 🥷

How to Identify a Recursive Problem? 🔍

1. Self-Replication: If a function can be defined in terms of itself, recursion is a strong candidate! 🚀

2. Base Case Matters: Can solving a small version of the problem help solve the bigger one? ✅

3. Choices, Choices Everywhere!: If you're making decisions at each step (like including/excluding elements), recursion might be the way. 🔄

💡 Thinking Recursively:

The Key Concept of Recursion 🧩

Common Recursive Patterns 🔄

1️⃣ Include-Exclude Pattern 🎭

Example: Finding All Subsequences of a String 📜

2️⃣ Explore All Possible Ways 🌍

Example: Maze Problem 🏰

3️⃣ Choices & Decision Tree 🌳

Example: Generating Parentheses 👶

4️⃣ IBH (Induction, Base Case, Hypothesis) 🧠

Example: Tower of Hanoi 🗼

Final Thoughts 🏁

Dijkstra's Shortest Path Algorithm Implementation

Key Concepts

Dijkstra's Algorithm

Graph Representation

Code Breakdown

1. Class Definition: DirectedWeightedGraph

2. Function: insertEdge

3. Function: dijkstrasShortestPath

4. Main Function

Example

Cycle Detection in a Directed Graph

Approach

1. DFS Cycle Detection

2. BFS Cycle Detection (Kahn's Algorithm)

Code Explanation

Topological Sorting to Determine Course Order

Approach

Key Steps:

Code Explanation

Interleaving Two Strings

House Robber Problem

Solving the 0 1 Knapsack Problem: From Recursion to Dynamic Programming

1. Class Definition: `DirectedWeightedGraph`

2. Function: `insertEdge`

3. Function: `dijkstrasShortestPath`