DEV Community: Santhoshi Mary A

Idempotency Situation

Santhoshi Mary A — Wed, 25 Mar 2026 17:01:37 +0000

Understanding Idempotency through a Simple Wallet Transfer System

Introduction

In digital payment systems, the same request can sometimes be sent multiple times due to network retries, timeouts, or users clicking the payment button more than once. If the system processes the same request repeatedly, it can lead to serious issues like duplicate deductions or incorrect balances.

This is where Idempotency becomes important. Idempotency ensures that even if the same operation is executed multiple times, the result remains the same as if it were executed only once.

To understand this better, I experimented with a simple wallet transfer system using PostgreSQL and simulated duplicate transaction requests.

Setting up the tables

I started by creating two tables: one for accounts and another to store transaction records.

CREATE TABLE accounts (
id SERIAL PRIMARY KEY,
name TEXT NOT NULL,
balance INT NOT NULL CHECK (balance >= 0),
last_updated TIMESTAMP DEFAULT CURRENT_TIMESTAMP
);

CREATE TABLE transactions (
transaction_id TEXT PRIMARY KEY,
sender_id INT,
receiver_id INT,
amount INT,
status TEXT,
created_at TIMESTAMP DEFAULT CURRENT_TIMESTAMP
);

Then I inserted two users:

INSERT INTO accounts (name, balance)
VALUES
('Alice', 1000),
('Bob', 500);

Checking the table:

SELECT * FROM accounts ORDER BY id;

At this point:

Alice has 1000
Bob has 500

Performing a normal transfer

First, I performed a transfer of 200 from Alice to Bob using a unique transaction ID.

BEGIN;

INSERT INTO transactions (transaction_id, sender_id, receiver_id, amount, status)
VALUES ('txn_001', 1, 2, 200, 'SUCCESS');

UPDATE accounts
SET balance = balance - 200
WHERE id = 1;

UPDATE accounts
SET balance = balance + 200
WHERE id = 2;

COMMIT;

After checking:

SELECT * FROM accounts ORDER BY id;

Now:

Alice = 800
Bob = 700

And the transaction was recorded in the transactions table.

Simulating duplicate request

Now I simulated a duplicate request by executing the same transfer again with the same transaction ID.

BEGIN;

INSERT INTO transactions (transaction_id, sender_id, receiver_id, amount, status)
VALUES ('txn_001', 1, 2, 200, 'SUCCESS');

UPDATE accounts
SET balance = balance - 200
WHERE id = 1;

UPDATE accounts
SET balance = balance + 200
WHERE id = 2;

COMMIT;

This resulted in an error because the transaction_id already exists.

Observing the result

After the error, I ran:

ROLLBACK;

Then checked the balances:

SELECT * FROM accounts ORDER BY id;

The balances remained:

Alice = 800
Bob = 700

The duplicate transaction was not applied.

Why this works

The transactions table uses a PRIMARY KEY on transaction_id.

This ensures that:

each transaction is unique
duplicate requests are rejected
repeated execution does not change the result

Because the insert fails, the entire transaction is rolled back, preventing duplicate updates.

Improving with conflict handling

Instead of throwing an error, we can also handle duplicates gracefully using:

INSERT INTO transactions (transaction_id, sender_id, receiver_id, amount, status)
VALUES ('txn_002', 1, 2, 200, 'SUCCESS')
ON CONFLICT (transaction_id) DO NOTHING;

This prevents duplicate inserts without crashing the system.

What I learned

From this experiment, I understood that:

Repeating the same SQL operations can cause duplicate updates
The database does not automatically prevent duplicate business actions
Idempotency must be implemented explicitly
Using a transaction table with a unique transaction ID prevents duplicate processing

Conclusion

This experiment showed how duplicate requests can affect a wallet system and how idempotency helps prevent such issues.

By introducing a transaction table with a unique transaction ID, we can ensure that even if the same request is repeated, it is processed only once.

In simple terms, idempotency ensures that performing the same action multiple times does not change the result after the first successful execution.

This is a critical concept in building reliable financial systems where duplicate processing can lead to serious problems.

Durability

Santhoshi Mary A — Wed, 25 Mar 2026 16:33:53 +0000

Understanding Durability through a Simple Wallet Transfer System

Introduction

While using payment apps, we expect that once a transaction is completed, it should remain saved permanently. Even if the system crashes or restarts, the updated balance should not disappear.

This behavior is ensured by Durability, one of the ACID properties of a database. Durability guarantees that once a transaction is committed, its changes are permanently stored and will not be lost.

To understand this better, I experimented with a simple wallet transfer system using PostgreSQL and observed how committed data behaves after reconnecting to the database.

Setting up the table

I started by creating a basic table to store account details.

CREATE TABLE accounts (
id SERIAL PRIMARY KEY,
name TEXT NOT NULL,
balance INT NOT NULL CHECK (balance >= 0),
last_updated TIMESTAMP DEFAULT CURRENT_TIMESTAMP
);

Then I inserted two users:

INSERT INTO accounts (name, balance)
VALUES
('Alice', 1000),
('Bob', 500);

Checking the table:

SELECT * FROM accounts ORDER BY id;

At this point:

Alice has 1000
Bob has 500

Performing a successful transfer

First, I performed a transfer of 200 from Alice to Bob inside a transaction.

BEGIN;

UPDATE accounts
SET balance = balance - 200,
last_updated = CURRENT_TIMESTAMP
WHERE id = 1;

UPDATE accounts
SET balance = balance + 200,
last_updated = CURRENT_TIMESTAMP
WHERE id = 2;

COMMIT;

After running this, I checked the table again:

SELECT * FROM accounts ORDER BY id;

Now:

Alice = 800
Bob = 700

This confirms that the transaction was successfully committed.

Simulating a restart or reconnect

To test durability, I disconnected from the database and reconnected again (or restarted the session).

After reconnecting, I ran:

SELECT * FROM accounts ORDER BY id;

The balances were still:

Alice = 800
Bob = 700

This shows that the committed changes were permanently saved and not lost after reconnecting.

What happens if failure occurs before commit

Next, I considered what happens if the system fails before the transaction is committed.

BEGIN;

UPDATE accounts
SET balance = balance - 200
WHERE id = 1;

UPDATE accounts
SET balance = balance + 200
WHERE id = 2;

If the system crashes at this point before COMMIT, the transaction is incomplete.

After reconnecting, the balances will remain:

Alice = 1000
Bob = 500

This means uncommitted changes are not saved.

What happens if failure occurs after commit

Now consider a failure happening immediately after COMMIT.

BEGIN;

UPDATE accounts
SET balance = balance - 200
WHERE id = 1;

UPDATE accounts
SET balance = balance + 200
WHERE id = 2;

COMMIT;

If the system crashes after this, once we reconnect and check:

SELECT * FROM accounts ORDER BY id;

The balances will still be:

Alice = 800
Bob = 700

This proves that committed data is not lost.

How PostgreSQL ensures durability

PostgreSQL ensures durability using a mechanism called Write-Ahead Logging (WAL).

Before permanently updating the actual data, PostgreSQL first records the changes in a log. Once the transaction is committed, this log ensures that even if the system crashes, the database can recover and restore the committed data.

Because of this:

committed transactions are always preserved
uncommitted transactions are discarded
the database can recover correctly after failure

What I learned

From this experiment, I understood that:

Once a transaction is committed, the data is permanently saved
Reconnecting or restarting does not remove committed changes
If failure occurs before commit, changes are not saved
Durability applies only to committed transactions

Conclusion

This experiment helped me understand how durability works in a database system.

Durability ensures that once a transaction is committed, its changes remain saved even after crashes or restarts. This is very important in financial systems like wallet applications, where losing committed transactions could lead to serious issues such as money loss or incorrect balances.

In simple terms, durability guarantees that once a payment is successful, it will always remain successful.

Consistency

Santhoshi Mary A — Wed, 25 Mar 2026 16:08:03 +0000

Understanding Consistency through a Simple Wallet System

Introduction

When we use payment apps, we always expect our balance to be correct. We never imagine seeing a negative balance or invalid data in our account.

Behind the scenes, the database ensures that all data always follows certain rules. This is called Consistency in ACID properties.

Consistency ensures that the database always remains in a valid state. If any operation tries to break the rules, the database rejects it.

To understand this better, I experimented with a simple wallet system using PostgreSQL and tried performing operations that violate these rules.

Setting up the table

I started by creating a basic table to store account details.

CREATE TABLE accounts (
id SERIAL PRIMARY KEY,
name TEXT NOT NULL,
balance INT NOT NULL CHECK (balance >= 0),
last_updated TIMESTAMP DEFAULT CURRENT_TIMESTAMP
);

Then I inserted two users:

INSERT INTO accounts (name, balance)
VALUES
('Alice', 1000),
('Bob', 500);

Checking the table:

SELECT * FROM accounts ORDER BY id;

At this point:

Alice has 1000
Bob has 500

The important rule here is:

CHECK (balance >= 0)

This ensures that no account can have a negative balance.

Trying a valid update

First, I performed a normal valid operation.

UPDATE accounts
SET balance = balance - 200
WHERE id = 1;

Checking the table:

SELECT * FROM accounts ORDER BY id;

Now:

Alice has 800
Bob has 500

This works because the balance is still valid (not negative).

Resetting the data

Before testing invalid cases, I reset the balances.

UPDATE accounts SET balance = 1000 WHERE id = 1;
UPDATE accounts SET balance = 500 WHERE id = 2;

Trying to break consistency (negative balance)

Now I tried to directly assign a negative balance.

UPDATE accounts
SET balance = -100
WHERE id = 1;

This resulted in an error because the database does not allow values that violate the constraint.

After checking the table:

SELECT * FROM accounts ORDER BY id;

Alice still has 1000
Bob still has 500

The update was rejected completely.

Trying to deduct more than available balance

Next, I tried to deduct more money than Alice actually has.

UPDATE accounts
SET balance = balance - 1500
WHERE id = 1;

This again resulted in an error.

Checking the table:

SELECT * FROM accounts ORDER BY id;

Alice = 1000
Bob = 500

The database did not allow the balance to go negative.

Trying the same inside a transaction

I also tested the same scenario inside a transaction.

BEGIN;

UPDATE accounts
SET balance = balance - 1500
WHERE id = 1;

This failed immediately.

Then I ran:

ROLLBACK;

Checking the table again:

SELECT * FROM accounts ORDER BY id;

Alice = 1000
Bob = 500

Even inside a transaction, the constraint prevented invalid data.

What I observed

From these tests, I understood that:

The database enforces rules defined in the schema
Invalid updates are rejected immediately
The balance never becomes negative
The database always maintains a valid state

However, I also noticed that:

The database only checks constraints like balance >= 0
It does not automatically handle business rules like:
- validating transfer amount
- ensuring sender and receiver exist
- preventing incorrect transfers

These must be handled using application logic or transactions.

Conclusion

This experiment helped me understand how consistency is maintained in a database system.

Consistency ensures that the database always remains in a valid state by enforcing rules like constraints. Even if an invalid operation is attempted, the database prevents it from being applied.

In real-world systems like digital wallets, this plays a crucial role in preventing incorrect balances and maintaining data integrity.

While constraints ensure data validity, additional logic is required to enforce complete business correctness.

Consistency, along with other ACID properties, forms the foundation for building reliable financial systems.

Atomicity - Design a Reliable Wallet Transfer System with ACID Guarantees

Santhoshi Mary A — Wed, 25 Mar 2026 14:17:20 +0000

Understanding Atomicity through a Simple Wallet Transfer System

Introduction

While using payment apps, we usually don’t think about what happens behind the scenes. When we send money, we simply expect that if it leaves our account, it should reach the other person. There should never be a situation where money is deducted but not received.

This behavior is handled by the database using something called Atomicity. It ensures that a transaction either completes fully or does not happen at all.

To understand this better, I tried building a simple wallet transfer system using PostgreSQL and tested different cases to see how the database behaves.

Setting up the table

I started by creating a basic table to store account details.

CREATE TABLE accounts (
id SERIAL PRIMARY KEY,
name TEXT NOT NULL,
balance INT NOT NULL CHECK (balance >= 0),
last_updated TIMESTAMP DEFAULT CURRENT_TIMESTAMP
);

Then I inserted two users:

INSERT INTO accounts (name, balance)
VALUES
('Alice', 1000),
('Bob', 500);

Checking the table:

SELECT * FROM accounts ORDER BY id;

At this point:

Alice has 1000
Bob has 500

Trying a normal transfer

First, I wanted to see how a proper transfer works.

I made Alice send 200 to Bob inside a transaction.

BEGIN;

UPDATE accounts
SET balance = balance - 200,
last_updated = CURRENT_TIMESTAMP
WHERE id = 1;

UPDATE accounts
SET balance = balance + 200,
last_updated = CURRENT_TIMESTAMP
WHERE id = 2;

COMMIT;

After running this:

Alice’s balance became 800
Bob’s balance became 700

This is exactly what we expect. Both operations happened together.

Resetting the data

Before testing failures, I reset the balances.

UPDATE accounts SET balance = 1000 WHERE id = 1;
UPDATE accounts SET balance = 500 WHERE id = 2;

What if something breaks in the middle

Now comes the interesting part.

I started a transaction, deducted money from Alice, but intentionally made a mistake in the next query.

BEGIN;

UPDATE accounts
SET balance = balance - 200
WHERE id = 1;

UPDATE accounts
SET balanc = balance + 200
WHERE id = 2;

This gave an error because of the wrong column name.

Then I ran:

ROLLBACK;

After checking the table, I noticed:

Alice still had 1000
Bob still had 500

Even though the first update ran, it was not saved. The database completely ignored it because the transaction failed later.

Another failure after a valid query

Next, I tried a different approach.

BEGIN;

UPDATE accounts
SET balance = balance - 300
WHERE id = 1;

SELECT * FROM non_existing_table;

The second query failed because the table does not exist.

After rollback, the balances were still:

Alice = 1000
Bob = 500

Again, nothing changed.

Trying to break it using constraints

I then tried to transfer more money than Alice actually had.

BEGIN;

UPDATE accounts
SET balance = balance - 1500
WHERE id = 1;

UPDATE accounts
SET balance = balance + 1500
WHERE id = 2;




This failed because the balance cannot go below zero.

After rollback:

* Alice = 1000
* Bob = 500

No changes were made.



 What happens without a transaction

To really understand why transactions matter, I tried the same thing without using BEGIN and COMMIT.


UPDATE accounts
SET balance = balance - 200
WHERE id = 1;

UPDATE accounts
SET balanc = balance + 200
WHERE id = 2;


The first query succeeded, but the second failed.

After checking:

* Alice had 800
* Bob still had 500

This is a partial update. Money was deducted but not credited.


 What I learned

From all these tests, a few things became very clear:

* A transaction ensures that all steps are treated as a single unit
* If any step fails, the entire transaction is rolled back
* The database does not allow partial updates inside a transaction
* Without transactions, inconsistent data can occur very easily

This is why atomicity is critical for systems that handle money.



 Conclusion

This simple experiment helped me understand how databases protect data integrity during operations like money transfers.

Atomicity ensures that either everything happens or nothing happens. In real-world applications, this is what prevents issues like money loss or incorrect balances.

Even though the example was simple, the concept is very powerful and is used in all reliable financial systems.

how DNS resolver is happening.

Santhoshi Mary A — Mon, 23 Mar 2026 18:36:35 +0000

When you enter a webpage such as:

Google.com

This name is not understood by your computer.

Only IP addresses such as these are understood by computers:

142.250.190.78

How, then, does your system translate a website name into an IP address?

DNS resolution is the term for that procedure.

Let's take a step-by-step look at it in very basic terms
DNS: What is it?

DNS is an acronym for Domain Name System.

It functions similarly to an online phone book.

👉 You look for a name
👉 DNS provides the IP address (phone number).

For instance:

You enter www.google.com.
DNS provides the Google servers' IP address.
Step-by-Step: DNS Resolution Process
Step 1: Enter a Website

For instance:

Amazon.com

Amazon's IP address is now required by your browser.

Step 2: Check the Browser Cache

Your browser first verifies:

Am I familiar with this IP already?

It might already be stored in memory if you visited recently.

If discovered ->Done
If not, proceed to the following step.

Operating System Cache in Step Three

Your computer’s OS also keeps a small DNS cache.

If IP is located ->Completed
If not, proceed.
Step 4: Send the DNS Resolver a Request

Your request is now sent to a DNS resolver.

Typically, this is supplied by:

Your Internet service provider, or ISP
or a public DNS such as:
Google Public DNS
Cloudflare (1.1.1.1)

The role of the resolver:

Determine this domain's correct IP address.

Resolver Requests Root DNS Server in Step Five

A Root DNS Server is asked by the resolver:

Where can I locate domains ending in.com?

The root server responds:

Ask the TLD server for.com.

Step 6: Request TLD Server

Top Level Domain, or TLD
For instance,.com,.org, and.net

The resolver queries:

Where is Amazon.com located?

The TLD server responds:

Ask the reputable name server at Amazon.
Step 7: Consult the Authoritative Name Server

The resolver now queries:

What is www.amazon.com's IP address?

The authoritative server responds:

54.xx.xx

Step 8: You Receive Your IP Address Back

The resolver

returns IP to your computer.
stores it in the cache for later use.

Your browser is now aware of the connection location.

Step 9: Website Loads

Your current browser:

uses IP to connect to the server.
transmits an HTTP request
The website loads

How a request originates from cllient and reaches the server

Santhoshi Mary A — Mon, 23 Mar 2026 17:38:54 +0000

A precise series of events is triggered in milliseconds each time you hit Enter on a URL. This is the entire journey, reduced to what really counts.

Parsing URLs
The browser starts determining where to send the request after breaking down https://www.example.com/products into three parts: protocol (https), domain (www.example.com), and path (/products).
DNS Resolution
Instead of a domain name, the browser requires an IP address. After checking its cache and the OS cache, it queries a DNS Recursive Resolver, which returns the IP after tracing the response up through Root, TLD, and Authoritative name servers.

Browser -> Resolver -> Root NS -> TLD NS -> Authoritative NS
|
93.184.216.34 <-----+
3.TLS Handshake (HTTPS only)
For secure connections, both sides negotiate encryption. The server presents its SSL certificate, they agree on a cipher, and a shared session key is derived. All further communication is encrypted.

4.HTTP Request and Methods
The browser sends the actual request:
The HTTP method tells the server what action to perform on the resource.
HTTP Methods Explained
Method

GET Retrieve a resource

POST Create a new resource

PUT Replace a resource entirely

PATCH Partially update a resource

DELETE Remove a resource
5.Idempotency: An Essential Idea in API Design
Idempotency is the ability of the server to produce the same result when the same request is made once or several times. In distributed systems, this is crucial because servers need to behave consistently, networks fail, and clients retry.

If making a request ten times has the same impact on the server state as making it just once, then it is idempotent.
Idempotency by Method
Idempotent Methods:
GET
PUT
DELETE
Non-Idempotent Methods:
POST (usually)
PATCH (depends)

6.The request is processed by the server

The server

gets the request
Verifies authenticity
executes backend logic
database queries when necessary
gets ready to respond
7.Server Sends HTTP Response
With:

Status code
Headers
Body (HTML/JSON/etc.)
8.The response is rendered by the browser.

The web browser

Parses HTML
uses CSS
JavaScript is executed
makes more API requests
shows the user the page

IP address and Subnet

Santhoshi Mary A — Mon, 23 Mar 2026 16:22:30 +0000

What does an IP address mean?
Every device that is connected to a computer network has a unique number called an IP address (Internet Protocol address). An IP address is like a home address in that it tells the internet exactly where to send data, just like a postal address tells the delivery person exactly where to drop off your package.
There are two versions that people use today:

IPv4 is the older and most common format. Written as four groups of numbers with dots between them, like 192.168.1.1. There are about 4.3 billion possible addresses because each number can be between 0 and 255.
IPv6 is the newer format that was made to fix the problem of IPv4 running out. Written in hexadecimal, like this: 2001:0db8:85a3:0000:0000:8a2e:0370:7334. It can handle an almost infinite number of addresses.
Public IP Address vs. Private IP Address
IP Address
Given by the Internet Service Provider (ISP)
Used online
One of a kind around the world
IP for private use
Used in networks that are close by
Not directly reachable from the web

Private IP ranges:

10.0.0.0 to 10.255.255.255
172.16.0.0 to 172.31.255.255
192.168.0.0 to 192.168.255.255
The Parts of an IPv4 Address
There are 32 bits in an IPv4 address, and they are grouped into four octets, each with 8 bits.

168. 1. 10 11000000 10101000 00000001 00001010 There are two parts to every IP address:

Network part: This tells you which network the device is on.
Host part: Identifies the exact device on that network
What is a Subnet?

A Subnet (Subnetwork) is a smaller division of a large network.

Instead of having one large network with thousands of devices, we divide it into smaller networks

The Mask for the Subnet
A subnet mask is a 32-bit number that tells devices which part of an IP address belongs to the network and which part belongs to the host.
For example:
192.168.1.10 is the IP address.
255.255.255.0 is the subnet mask.
In binary:
IP: 11000000.10101000.00000001.00001010
Mask:11111111.11111111.11111111.00000000
The 1s in the mask are the network part.
The mask's 0s stand for the host part.
The first three octets (192.168.1) tell you which network you're on, and the last octet (.10) tells you which host you're on.

CIDR Notation
CIDR (Classless Inter-Domain Routing) notation is a way to write the subnet mask in a short way by counting the number of 1-bits.
192.168.1.0/24 → 255.255.255.0 (the mask has 24 ones)
10.0.0.0/8 → 255.0.0.0 (the mask has 8 ones in it)
172.16.0.0/16 → 255.255.0.0 (the mask has 16 ones in it)

Note: Two addresses in every subnet are always reserved — one for the network address and one for the broadcast address — which is why usable hosts = total addresses minus 2.

Network Address — First address of a subnet (not assignable to a host)
Broadcast Address — Last address of a subnet (sends data to all hosts in the subnet)

Sort a Linked List using Merge Sort

Santhoshi Mary A — Sun, 22 Mar 2026 14:05:42 +0000

Problem Statement

Given the head of a singly linked list, sort the linked list using Merge Sort.

Constraints:

1 ≤ number of nodes ≤ 10⁵
0 ≤ node.data ≤ 10⁶
Example 1

Input:

40 -> 20 -> 60 -> 10 -> 50 -> 30

Output:

10 -> 20 -> 30 -> 40 -> 50 -> 60
Example 2

Input:

9 -> 5 -> 2 -> 8

Output:

2 -> 5 -> 8 -> 9
Why Merge Sort for Linked List?

Merge Sort is preferred for linked lists because:

It does not require random access.
It works efficiently with pointers.
Time Complexity is O(n log n).
Space Complexity is O(1) (excluding recursion stack).

Unlike arrays, quick sort is not efficient for linked lists due to lack of indexing.

Approach Overview

Merge Sort works in three main steps:

Find the middle of the linked list.
Divide the list into two halves.
Recursively sort both halves.
Merge the two sorted halves.
Step 1 – Finding the Middle

We use the slow and fast pointer method.

Slow moves 1 step.
Fast moves 2 steps.
When fast reaches end, slow will be at middle.
Step 2 – Divide the List

After finding middle:

Break the list into two halves.
Call mergeSort recursively on both halves.
Step 3 – Merge Two Sorted Lists

Compare nodes from both lists.
Attach the smaller node to result.
Repeat until one list finishes.

Python Implementation
class Solution:

def mergeSort(self, head):
    # Base case
    if not head or not head.next:
        return head

    # Step 1: Find middle
    middle = self.getMiddle(head)
    next_to_middle = middle.next
    middle.next = None

    # Step 2: Divide and sort
    left = self.mergeSort(head)
    right = self.mergeSort(next_to_middle)

    # Step 3: Merge sorted halves
    sorted_list = self.sortedMerge(left, right)

    return sorted_list


def getMiddle(self, head):
    if not head:
        return head

    slow = head
    fast = head.next

    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

    return slow


def sortedMerge(self, left, right):
    if not left:
        return right
    if not right:
        return left

    if left.data <= right.data:
        result = left
        result.next = self.sortedMerge(left.next, right)
    else:
        result = right
        result.next = self.sortedMerge(left, right.next)

    return result

Dry Run Example

Input:

9 -> 5 -> 2 -> 8

Step 1:
Split into:

9 -> 5
2 -> 8

Step 2:
Split again:

9 | 5
2 | 8

Step 3:
Merge:

5 -> 9
2 -> 8

Final Merge:

2 -> 5 -> 8 -> 9
Time and Space Complexity

Time Complexity: O(n log n)

Each level divides list into halves.
Merging takes O(n).

Space Complexity: O(log n)

Due to recursion stack.
Why This Works Efficiently

Linked lists allow easy splitting and merging using pointer manipulation.

No extra array is needed.
No shifting of elements.
Only pointer adjustments.

Remove Duplicates in Sorted Linked List

Santhoshi Mary A — Sun, 22 Mar 2026 14:01:59 +0000

Problem Statement

Given a sorted singly linked list, remove duplicate nodes so that each element appears only once.

Important:

The list is already sorted.
Do not use extra space.
Modify the list in-place.
Return the head of the updated list.
Example 1

Input:

2 -> 2 -> 4 -> 5

Output:

2 -> 4 -> 5

Explanation:
The value 2 appears twice. Since the list is sorted, duplicates are adjacent. We remove one occurrence.

Example 2

Input:

2 -> 2 -> 2 -> 2 -> 2

Output:

Explanation:
All elements are the same. We keep only one node and remove the rest.

Key Observation

Because the linked list is sorted, duplicate values will always appear next to each other.

That means we don’t need:

Extra data structures
Nested loops
Hashing

We can solve it using a single traversal.

Approach (Single Traversal)
Idea
Start from the head.
Compare the current node with its next node.
If both values are equal:
Skip the next node.
Otherwise:
Move forward.
Python Implementation
def removeDuplicates(head):
curr = head

while curr and curr.next:
    if curr.data == curr.next.data:
        curr.next = curr.next.next
    else:
        curr = curr.next

return head

How It Works (Step-by-Step)

Let’s take:

2 -> 2 -> 4 -> 5
Step 1:
curr = first 2
curr.data == curr.next.data → duplicate found
Skip next node

List becomes:

2 -> 4 -> 5
Step 2:
curr moves to 4
4 != 5 → move forward
Step 3:
curr moves to 5
End of list

Final Result:

2 -> 4 -> 5

Reverse a Linked List

Santhoshi Mary A — Sun, 22 Mar 2026 13:57:23 +0000

Problem Statement

Given the head of a linked list, reverse the list and return the new head.

Example

Input:

1 → 2 → 3 → 4 → 5 → NULL

Output:

5 → 4 → 3 → 2 → 1 → NULL
Table of Contents
Approach – Iterative Method (O(n) Time | O(1) Space)
Alternate Approach 1 – Recursion (O(n) Time | O(n) Space)
Alternate Approach 2 – Using Stack (O(n) Time | O(n) Space)

Approach – Iterative Method (Most Optimal) Idea

We reverse the linked list by changing the direction of links using three pointers:

prev
curr
next_node

At each step:

Store next node.
Reverse current node’s pointer.
Move all pointers one step forward.

We repeat this until the list becomes NULL.

Step-by-Step Logic

Initial state:

prev = NULL
curr = head

While curr is not NULL:

Save next node → next_node = curr.next
Reverse link → curr.next = prev
Move prev forward → prev = curr
Move curr forward → curr = next_node

At the end:

prev becomes the new head.
Python Code (Iterative – O(1) Space)
class Solution:
def reverseList(self, head):
prev = None
curr = head

    while curr:
        next_node = curr.next   # Store next node
        curr.next = prev        # Reverse the link
        prev = curr             # Move prev forward
        curr = next_node        # Move curr forward

    return prev

Time and Space Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Why O(1)?
Because we are only using three pointers.

Find the Majority Element

Santhoshi Mary A — Sun, 22 Mar 2026 13:53:35 +0000

Problem Statement

Given an array arr[], find the majority element.

A majority element is defined as an element that appears strictly more than n/2 times in the array.

If no such element exists, return -1.

Example 1

Input:

arr = [1, 1, 2, 1, 3, 5, 1]

Output:

Explanation:
Array size = 7
n/2 = 3.5
Element 1 appears 4 times → 4 > 3.5 → Majority element

Example 2

Input:

arr = [7]

Output:

Explanation:
Array size = 1
7 appears once → 1 > 0.5 → Majority element

Example 3

Input:

arr = [2, 13]

Output:

-1

Explanation:
Array size = 2
n/2 = 1
No element appears more than 1 time

Efficient Approach – Moore’s Voting Algorithm

Instead of counting frequencies using a dictionary (O(n) space),
we use Moore’s Voting Algorithm which works in:

Time Complexity: O(n)
Space Complexity: O(1)

Why Moore’s Voting Works

If a majority element exists:

It will survive pairwise cancellation.
Other elements cancel each other out.
The majority element remains as candidate.

The algorithm works in two phases:

Find a candidate
Verify the candidate
Step 1 – Find Candidate

We maintain:

candidate
count

Traverse the array:

If count == 0 → choose new candidate
If element == candidate → increase count
Else → decrease count
Step 2 – Verify Candidate

Count how many times the candidate appears.
If it appears more than n/2 times → return it.
Otherwise → return -1.

Python Code (Optimized O(n) Solution)
class Solution:
def majorityElement(self, arr):
count = 0
candidate = None

    # Step 1: Find potential candidate
    for num in arr:
        if count == 0:
            candidate = num
            count = 1
        elif num == candidate:
            count += 1
        else:
            count -= 1

    # Step 2: Verify candidate
    if arr.count(candidate) > len(arr) // 2:
        return candidate

    return -1

Dry Run Example

Input:

[1, 1, 2, 1, 3, 5, 1]

Iteration process:

candidate = 1, count = 1
candidate = 1, count = 2
count decreases (2 encountered)
candidate = 1, count = 2
count decreases (3 encountered)
count decreases (5 encountered)
candidate = 1, count = 1

Final candidate = 1
Verify → appears 4 times
4 > 7//2 → return 1

Why This Is Optimal

Brute Force → O(n²)
Using dictionary → O(n) time + O(n) space
Moore’s Voting → O(n) time + O(1) space

Search in Rotated Sorted Array

Santhoshi Mary A — Sun, 22 Mar 2026 13:50:44 +0000

Problem Statement

You are given a sorted array that has been rotated at some unknown index.

Example:

Original sorted array:

[0,1,2,4,5,6,7]

After rotating left by 3:

[4,5,6,7,0,1,2]

Given:

Rotated sorted array nums
A target value target

Return:

The index of target if found
-1 if not found

⚡ Required Time Complexity: O(log n)

Example 1

Input:

nums = [4,5,6,7,0,1,2]
target = 0

Output:

4
Example 2

Input:

nums = [4,5,6,7,0,1,2]
target = 3

Output:

-1
Important Observation

Even though the array is rotated:

At least one half of the array is always sorted.
We can use Binary Search logic cleverly.
Key Idea

At every step:

Find mid
Check which half is sorted:
Left half sorted?
Right half sorted?
Check if target lies inside the sorted half.
Narrow the search space accordingly.

This ensures O(log n) complexity.

Step-by-Step Logic

Inside while loop:

Case 1: Left Half is Sorted

If:

nums[left] <= nums[mid]

Then:

If target lies between nums[left] and nums[mid]
→ Search left half
Else
→ Search right half
Case 2: Right Half is Sorted

Else:

If target lies between nums[mid] and nums[right]
→ Search right half
Else
→ Search left half
Python Implementation (O(log n))
class Solution:
def search(self, nums, target):
left = 0
right = len(nums) - 1

    while left <= right:
        mid = (left + right) // 2

        # If target found
        if nums[mid] == target:
            return mid

        # Check if left half is sorted
        if nums[left] <= nums[mid]:

            # Target lies in left sorted half
            if nums[left] <= target < nums[mid]:
                right = mid - 1
            else:
                left = mid + 1

        # Otherwise right half is sorted
        else:

            # Target lies in right sorted half
            if nums[mid] < target <= nums[right]:
                left = mid + 1
            else:
                right = mid - 1

    return -1

Time and Space Complexity

Time Complexity: O(log n)
Space Complexity: O(1)

Why This Works

Even after rotation:

The array is divided into two halves.
One half will always remain sorted.
Binary search reduces search space by half each iteration.
Edge Cases Covered

Array size = 1
Target not present
No rotation (normal sorted array)
Rotation at last index