DEV Community: Addy

An efficient approach to problem solving for DSA

Addy — Mon, 09 Jun 2025 05:49:21 +0000

Starting to solve DSA problems might seem scary to many and some might have started but failed to continue it for a significiant amount of time. So, why does this happen? What are you lacking? A structured problem solving approach.

You don't read the problem statement and straight away dive to code the solution. That's not what a wise person does and its not something to be ashamed of. Before coding up the solution you first need to understand the problem and plan the algorithm beforehand and test it yourself. Then you can implement it which would not take much time then.

Now comes the main question, how do you start then?

First of all, you should read the question properly and should understand the question well enough, the input format, the output format needed. The core question might be layered with an extra complexity by adding some useless info. You need to extract the core question that the problem asks.
For example, look at this leetcode question below (198. House Robber)

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.

The question added unnecessary entities like money, police, robber, house. You don't need to know them for solving the question. You just need numbers and data structures. Its mentioned in the end that you are given an array representing the amount of money, therefore the input is an array of numbers.

On reading the first paragraph carefully or several times if you need to, you can come to a conclusion that at its core, it just asks you this basic thing

Return the maximum sum of non-adjacent array elements from the given input array of numbers.

This core question was coated with many things to confuse the readers and take their time. Now if you get this you can start to focus on the problem that you got now.

Whenever you solve a question always make yourself clear what is the problem you're solving? Break that problem to smaller test-cases, list them and tackle them in an isolated manner by completely focusing on the sub-problem. As you solve the sub-problems, tick them in your list to boost your motivation. Once you tick all the problems, bam! you solved the main problem.

For solving a problem use the PBOI approach. It is an acronym for

P - Pen & Paper

B - Bruteforce

O - Optimize the bruteforce

I - Only now, Implement

Think of the testcases or use the given ones and solve by yourself on paper. It would be pretty easy to solve for you unless some recursion is involved. So, better start with a small testcase.

Now, slow down and carefully go through the process your brain follows to solve the testcase. Translate your brain's process on paper using the steps that computers could understand and perform. This process will take time and you will improve by time and practice.

Once you have the steps, congratulations! that's what you call an algorithm. The next step for you would be to turn this algorithm into pseudo-code. If your programming knowledge is good this step won't be tough.

Now take a test-case, and don't solve by your brain this time, but solve using the pseudo-code that you wrote on paper. Go line by line and pass the control of the program as a real computer would do. Track the variables and data structures on paper and update them at each line. This process is called dry-running the problem.

This helps you by saving time from implementing a wrong solution and then banging your head. If there was a problem in your algorithm, you'd find right away at the time of dry-run and then you can fix it there. This approach would save a lot of time and is efficient.

Once you get a working algorithm, calculate the time complexity of your algorithm and try to optimize it even further on paper itself. You don't need to implement that bruteforce if it working on dry-run. It would just boost your ego. Try to optimize it and after trying enough if you were able to good, else you still have a bruteforce approach.

Finally, comes the step for implementation. Now as you have an optimized algorithm and a pseudo-code for the problem, you can easily implement it in a programming language if your syntactically good in your preferred lanugage.

This was a structured problem solving approach that many of the programmers use. Some knowingly and some unknowingly.

Now, you might be thinking how much time should I try devising a working algorithm? I'd say if you're new to a concept, you should give 45-60 minutes and if you're familiar with the concept you should try for 30 minutes and then look for solutions.

When you look for the solution, you don't have to copy paste it directly, but rather you have to dry-run the found solution to get a deep understanding of the algorithm that is used. In the implementation part too, you don't copy-paste the solution. You should type by yourself because this helps in even deeper understanding of the solution. Copy-pasting might make you feel good to see all the test-cases passing, but in a longer run you won't learn anything. Even if you try other's solution, NEVER COPY-PASTE.

Thank you for reading! Don't forget to leave a like if this blog post has helped you and follow for more such content.

Disjoint Set Union / Union Find Algorithm Simplified

Addy — Sun, 08 Jun 2025 18:06:11 +0000

Union Find algorithm is a crucial algorithm in problems related to graph data structure. It helps find the relation between vertices by using the existing edges and tells whether the two are related or not.

It is very useful in real-world scenarios like for example, LinkedIn uses this algorithm to display the users information about the degree of connection with other users. People who are direct parent to the user are the 1st level connection, people who are the parent of the parent of the user are the 2nd level connection and so on.

You might be thinking what is this parent thing I mentioned so much about? It's just a directed edge between the two nodes, in our case, an edge from user to another person makes and edge like user -> another person. In real life it translates to user "follows/is a friend of" another person.

Union Find algorithm includes two methods:

Find - to get the root representative of the set in which the current vertex belongs to. (uses Path Compression for optimization)
Union - Tells whether the two vertices are in the same set or not, and if not merges them into a single set. (uses Rank to decide the resultant merged set)

Here, are some basic things we should know before diving in:

Each vertex initially belongs to its own set, and therefore is the root representative of that set. It is implemented as an array generally.
Each vertex initially is assigned the same rank which others have, here we assign 0. It is also implemented as an array generally.

Let's implement the find() method first as it is required in the union() method later.

int find(int i, int[] parent)

We take a vertex i and the parent array to find the root representative of the vertex i and return it.

int root = parent[i];

We get the parent of the i from the array. Initially we would get the element itself, if there are no relations (merging) yet.

// parent of the vertex is not the root representative
if (root != parent[root])
    return parent[i] = find(root, parent);

// parent of the vertex is the root representative
return root;

First, we check if the parent of the vertex is the root of the set to which the vertex belongs to? if yes then we simply return it, as it was the main goal of our function.

But, if not, then we recursively try to find the root until the parent and vertex are same and assign it in the parent array.

Think of it like this, if the vertex and the parent of vertex are the same, then it is the root representative of the set in which it belongs. Once we find it we return it.

For a more clearer visual representation of the find() function refer this image

Here, as you can see the path from 7 to the root (ie. 1) was from 7 -> 3 -> 1 and after calling find(7) which in turn calls find(3) and later assigns the parent of 7 as 1. It can be clearly seen from the image that the path is reduced, keeping all the vertices still in the same set. Just we get the compressed path of the root of the vertex from this function.

Now, comes the union() method. After understanding find(), it is just a piece of cake.

boolean union(int i, int j, int[] parent, int[] rank)

We take the two vertices to unite into a single set, the parent array and the rank array.

int iRoot = find(i, parent);
int jRoot = find(j, parent);

// both vertices belong to the same set already
if (iRoot == jRoot)
    return false;

Firstly, we just get the roots of both the vertices using the previously defined find() method.

If the roots returned by both the method calls are same, then it would simply mean that they are already in the same set and we can't unite it further. That's why we return false.

if (rank[iRoot] > rank[jRoot])
    parent[jRoot] = iRoot;

else if (rank[iRoot] < parent[jRoot])
    parent[iRoot] = jRoot;

Now, just compare the ranks of both vertices and merge the smaller ranking vertex to the set of the greater ranking vertex. Now you might think, if we don't modify the rank here, then how they can be compared in the first place? We modify the rank when the ranks of both vertices are found to be same.

else {
    parent[iRoot] = jRoot;
    rank[jRoot]++;
}

We can merge any vertex into the other vertex's set, but we have to make sure that we increase the rank of the set in which the vertex have been merged or rather "united" by 1.

return true;

At the end of the if-else ladder, if we reach there, we return true. It indicates that the vertices have been "united" to a single set and the "union" operation was successful!

You can implement this in any language as the syntax used here is generic and can be applied to implement in most of the languages with little to no change.

I have implemented it in java and here is the full code for reference.

public class DSU {
    // finds the root of a given vertex's set with path compression
    private static int find(int i, int[] parent) {
        // the root is not the vertex itself
        int root = parent[i];

        // the root of this vertex isn't the root of the set
        if (root != parent[root])
            // update the current vertex's parent with the root of its 
            // current parent's root to compress path
            return parent[i] = DSU.find(root, parent);

        // the root of this vertex is also the root of the set
        return root;
    }

    // checks the root of both the vertices and assign new roots 
    private static boolean union(int i, int j, int[] parent, int[] rank) {
        int iRoot = DSU.find(i, parent);
        int jRoot = DSU.find(j, parent);

        if (iRoot == jRoot)
            return false;

        if (rank[iRoot] > rank[jRoot])
            parent[jRoot] = iRoot;

        else if (rank[iRoot] < parent[jRoot])
            parent[iRoot] = jRoot;

        else {
            parent[iRoot] = jRoot;
            rank[jRoot]++;
        }

        return true;
    }
}

Thank you for reading! Follow me and stay tuned in for more such simplified explanations.

Migrating to Prisma Postgres Global DB from postgreSQL DB with Prisma ORM

Addy — Sat, 07 Jun 2025 11:26:03 +0000

Recently Prisma came with an update and launched its new global database called Prisma Postgres. It's a great option for our deploys as it saves the time and money for searching other platforms and providers to host our database online. It provides 5 databases with 1 GB storage for its free plan users.

If you are a Prisma user with postgreSQL database then the below mentioned steps in this blogpost would help you easily migrate all your data from the old database to the new global database. So let's just begin directly!

Step 1

Create a new database in Prisma Console

Step 2

Go to Database > Setup > Existing Project > Generate database credentials

Step 3

On clicking the generate button, your new database details (connection url + api key) would be shown, store them in your .env file of the project.

Step 4

Now, open up a terminal and get your old database's connection url and enter the following command

pg_dump -Fc -v -d DATABASE_URL -n public -f db_dump.bak

This will create a bak file which will have your all previous data with the name db_dump.

Step 5

Set the environment variable in the terminal explicitly by running the following command

export DATABASE_URL="prisma+postgres://accelerate.prisma-data.net/?api_key=API_KEY"

Use the API_KEY which was received in step 3.

Step 6

Open up a bash terminal (if you weren't using it in earlier steps) and enter the following command to start a tunnel.

npx @prisma/ppg-tunnel --host 127.0.0.1 --port 5433

If this runs properly, you won't be able to use that terminal now further. Open up a new terminal, but don't close the previous one, as it runs our tunnel.

Step 7

Now comes the final command to transfer the data, enter it and you're good to go

PGSSLMODE=disable pg_restore -h 127.0.0.1 -p 5433 -v -d postgres ./db_dump.bak && echo "-complete-"

A message "-complete-" would appear on successful transfer of the data. For further verification, you can run

npx prisma studio

with the new database connection url in your .env to check whether the old data is there in your new database or not.

Reference

Import from existing Postgres database into Prisma Postgres | Prisma Documentation

Learn how to import data from an existing database into Prisma Postgres.

prisma.io