DEV Community: Sruthika Ramachandran

Different Sorting Methodologies

Sruthika Ramachandran — Sun, 22 Mar 2026 17:46:17 +0000

Introduction

Sorting is one of the most fundamental operations in computer science.
It involves arranging data in a specific order (ascending or descending).

Efficient sorting helps improve the performance of searching and data processing tasks.

In this blog, we will explore three basic sorting algorithms:

Bubble Sort
Selection Sort
Insertion Sort

1. Bubble Sort

Concept

Bubble Sort repeatedly compares adjacent elements and swaps them if they are in the wrong order.

Larger elements “bubble up” to the end of the list.

Algorithm

Compare adjacent elements
Swap if needed
Repeat for all elements
Continue until array is sorted

Code (Python)

def bubble_sort(arr):
    n = len(arr)

    for i in range(n):
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]

    return arr

Complexity

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

Key Point

Simple to understand
Not efficient for large data

2. Selection Sort

Concept

Selection Sort selects the smallest element from the unsorted part and places it at the correct position.

Algorithm

Find minimum element
Swap it with first element
Repeat for remaining array

Code (Python)

def selection_sort(arr):
    n = len(arr)

    for i in range(n):
        min_index = i

        for j in range(i + 1, n):
            if arr[j] < arr[min_index]:
                min_index = j

        arr[i], arr[min_index] = arr[min_index], arr[i]

    return arr

Complexity

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

Key Point

Fewer swaps compared to Bubble Sort
Still inefficient for large inputs

3. Insertion Sort

Concept

Insertion Sort builds the sorted array one element at a time by inserting elements into their correct position.

Algorithm

Take one element
Compare with previous elements
Insert it in correct position
Repeat for all elements

Code (Python)

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1

        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1

        arr[j + 1] = key

    return arr

Complexity

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

Key Point

Efficient for small or nearly sorted data
Used in real-world hybrid algorithms

Conclusion

Sorting algorithms are essential building blocks in programming.

Bubble Sort is easiest to understand
Selection Sort reduces swaps
Insertion Sort is efficient for small datasets.

Sort a Linked List using Merge Sort

Sruthika Ramachandran — Sun, 22 Mar 2026 17:26:14 +0000

Introduction

Sorting is a fundamental operation in programming.

While arrays can be sorted easily, linked lists require a different approach.
The most efficient way to sort a linked list is using Merge Sort, because it works well with linked structures.

Problem Statement

Given the head of a linked list,
sort the list using Merge Sort and return the sorted list.

Examples

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

Intuition

Merge Sort follows Divide and Conquer:

Divide list into two halves
Recursively sort both halves
Merge sorted halves

Approach (Merge Sort)

Algorithm Steps

Find middle of list
- Use slow & fast pointer
Split list into two halves
Recursively sort both halves
Merge the two sorted lists

Code (Python)

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

# Merge two sorted lists
def merge(l1, l2):
    dummy = ListNode(0)
    tail = dummy

    while l1 and l2:
        if l1.val < l2.val:
            tail.next = l1
            l1 = l1.next
        else:
            tail.next = l2
            l2 = l2.next
        tail = tail.next

    tail.next = l1 if l1 else l2
    return dummy.next

# Find middle of list
def get_middle(head):
    slow, fast = head, head.next

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

    return slow

def merge_sort(head):
    if not head or not head.next:
        return head

    mid = get_middle(head)
    right = mid.next
    mid.next = None

    left = merge_sort(head)
    right = merge_sort(right)

    return merge(left, right)

Step-by-Step Explanation

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

Split -> [40,20,60] and [10,50,30]
Recursively split further
Merge sorted parts
Final -> sorted list

Complexity Analysis

Time Complexity: O(n log n)
Space Complexity: O(log n) (recursion stack)

Conclusion

Merge Sort is the most efficient and preferred method to sort linked lists.
It demonstrates divide-and-conquer and pointer manipulation techniques.

Remove Duplicates in Sorted Linked List

Sruthika Ramachandran — Sun, 22 Mar 2026 17:22:36 +0000

Introduction

Linked Lists often contain duplicate values, especially when data is sorted.

This problem focuses on removing duplicate nodes from a sorted linked list while maintaining the original structure.

Problem Statement

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

Conditions:

The list is already sorted
Do not use extra space
Modify the list in-place

Examples

Example 1:
Input: 2 -> 2 -> 4 -> 5
Output: 2 -> 4 -> 5

Example 2:
Input: 2 -> 2 -> 2 -> 2 -> 2
Output: 2

Intuition

Since the list is sorted, duplicates will always be adjacent.

So:

Compare current node with next node
If equal -> skip the next node
Else -> move forward

Approach

Algorithm Steps

Start with current = head
Traverse the list:
- If current.val == current.next.val:
  - Skip duplicate -> current.next = current.next.next
- Else:
  - Move to next node
Continue until end

Code (Python)

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def removeDuplicates(head):
    current = head

    while current and current.next:
        if current.val == current.next.val:
            current.next = current.next.next  # remove duplicate
        else:
            current = current.next

    return head

Step-by-Step Explanation

For 2 -> 2 -> 4 -> 5:

Compare 2 and 2 -> remove duplicate
Move to 4 -> no duplicate
Move to 5 -> no duplicate

Final → 2 -> 4 -> 5

Complexity Analysis

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

Conclusion

Removing duplicates from a sorted linked list is a simple yet powerful problem that demonstrates efficient pointer usage and optimization techniques.

Reverse a Linked List

Sruthika Ramachandran — Sun, 22 Mar 2026 17:18:10 +0000

Introduction

Linked Lists are an important data structure where elements are connected using pointers.

One of the most fundamental operations is reversing a linked list, which helps in understanding pointer manipulation.

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

Intuition

Reverse the direction of each link
Instead of pointing forward, each node should point backward

Approach

Algorithm Steps

Initialize:
- prev = None
- curr = head
Traverse the list:
- Store next node
- Reverse current node’s pointer
- Move prev and curr forward
Return prev as new head

Code (Python)

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def reverseList(head):
    prev = None
    curr = head

    while curr:
        next_node = curr.next
        curr.next = prev
        prev = curr
        curr = next_node

    return prev

Step-by-Step Explanation

For 1 -> 2 -> 3 -> 4 -> 5:

Step 1 -> 1 -> NULL
Step 2 -> 2 -> 1
Step 3 -> 3 -> 2 -> 1
Continue until full reversal

Complexity Analysis

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

Conclusion

Reversing a linked list is a fundamental problem that builds strong understanding of pointer manipulation.

Find the Majority Element

Sruthika Ramachandran — Sun, 22 Mar 2026 17:13:49 +0000

Introduction

In many problems, we need to identify the most frequent element in an array.

The majority element is the one that appears more than n/2 times.

This problem can be solved efficiently using the Boyer-Moore Voting Algorithm, which is optimal.

Problem Statement

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

Conditions:

Majority element appears more than n/2 times
If no such element exists -> return -1

Examples

Example 1:
Input: [1, 1, 2, 1, 3, 5, 1]
Output: 1

Example 2:
Input: [7]
Output: 7

Example 3:
Input: [2, 13]
Output: -1

Intuition

Majority element dominates all others combined
We cancel out different elements

Approach

Algorithm Steps

Initialize:
- candidate = None
- count = 0
Traverse array:
- If count == 0 -> set new candidate
- If element == candidate -> increment count
- Else -> decrement count
Verify candidate:
- Count its frequency
- If > n/2 -> return candidate
- Else -> return -1

Code (Python)

def majority_element(arr):
    candidate = None
    count = 0

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

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

Step-by-Step Explanation

For [1, 1, 2, 1, 3, 5, 1]:

Start -> candidate = 1
Match -> increase count
Different -> decrease count
Majority survives cancellation

Final -> candidate = 1

Complexity Analysis

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

Conclusion

The algorithm is an elegant solution for finding the majority element efficiently.

Search in Rotated Sorted Array

Sruthika Ramachandran — Sun, 22 Mar 2026 16:57:03 +0000

Introduction

Binary Search works efficiently on sorted arrays.
But what if the array is rotated?

This problem teaches how to apply binary search even when the array is not fully sorted but partially sorted.

Problem Statement

You are given a sorted array nums that is rotated at an unknown index.

Task:
Find the index of a target element.
If not found, return -1.

Constraint:

Time complexity must be O(log n)

Examples

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

Example 3:
Input: nums = [1], target = 0
Output: -1

Intuition

Even though the array is rotated, one half is always sorted.

So:

Check which half is sorted
Decide where the target lies
Apply binary search accordingly

Approach

Algorithm Steps

Initialize:
- low = 0, high = n - 1
While low <= high:
- Find mid: mid = (low + high) // 2
- If nums[mid] == target-> return mid
Check sorted half:
- If left half is sorted (nums[low] <= nums[mid]):
  - If target lies in left -> search left
  - Else -> search right
- Else right half is sorted:
  - If target lies in right -> search right
  - Else -> search left

Code (Python)

def search(nums, target):
    low, high = 0, len(nums) - 1

    while low <= high:
        mid = (low + high) // 2

        if nums[mid] == target:
            return mid

        # Left half is sorted
        if nums[low] <= nums[mid]:
            if nums[low] <= target < nums[mid]:
                high = mid - 1
            else:
                low = mid + 1

        # Right half is sorted
        else:
            if nums[mid] < target <= nums[high]:
                low = mid + 1
            else:
                high = mid - 1

    return -1

Step-by-Step Explanation

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

mid = 7 -> left sorted
target not in left -> go right
mid = 1 -> found

Complexity Analysis

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

Conclusion

This problem is a powerful extension of binary search and is frequently asked in technical interviews.

First & Last Occurences

Sruthika Ramachandran — Sun, 22 Mar 2026 16:51:14 +0000

Introduction

Searching in a sorted array can be optimized using Binary Search.

This problem extends binary search to find not just one occurrence, but the first and last positions of a target element.

Problem Statement

Given a sorted array arr[] (may contain duplicates) and a value x,

Find:

First occurrence of x
Last occurrence of x

If not found, return [-1, -1]

Examples

Example 1:
Input: arr = [1, 3, 5, 5, 5, 5, 67, 123, 125], x = 5
Output: [2, 5]

Example 2:
Input: arr = [1, 3, 5, 5, 5, 5, 7, 123, 125], x = 7
Output: [6, 6]

Example 3:
Input: arr = [1, 2, 3], x = 4
Output: [-1, -1]

Intuition

Normal binary search finds any one occurrence

But we need:

First occurrence -> go left
Last occurrence -> go right

Approach

Algorithm Steps

Step 1: Find first occurrence

If found, move left (high = mid - 1)

Step 2: Find last occurrence

If found, move right (low = mid + 1)

Code (Python)

def find_first(arr, x):
    low, high = 0, len(arr) - 1
    first = -1

    while low <= high:
        mid = (low + high) // 2

        if arr[mid] == x:
            first = mid
            high = mid - 1   # move left
        elif arr[mid] < x:
            low = mid + 1
        else:
            high = mid - 1

    return first


def find_last(arr, x):
    low, high = 0, len(arr) - 1
    last = -1

    while low <= high:
        mid = (low + high) // 2

        if arr[mid] == x:
            last = mid
            low = mid + 1   # move right
        elif arr[mid] < x:
            low = mid + 1
        else:
            high = mid - 1

    return last


def find_occurrences(arr, x):
    return [find_first(arr, x), find_last(arr, x)]

Step-by-Step Explanation

For x = 5:

First occurrence -> move left until smallest index
Last occurrence -> move right until largest index

Complexity Analysis

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

Conclusion

This problem is a great example of extending binary search for more advanced queries like range finding.

Squares of a Sorted Array

Sruthika Ramachandran — Sun, 22 Mar 2026 16:45:14 +0000

Introduction

Given a sorted array, squaring each element may disturb the order because negative numbers become positive.

The challenge is to return the squared values in sorted order efficiently, without using an extra sorting step.

Problem Statement

Given an integer array nums sorted in non-decreasing order,
return an array of the squares of each number, also sorted in non-decreasing order.

Examples

Example 1:
Input: [-4, -1, 0, 3, 10]
Output: [0, 1, 9, 16, 100]

Example 2:
Input: [-7, -3, 2, 3, 11]
Output: [4, 9, 9, 49, 121]

Intuition

The largest square comes from either:
- The most negative number (left side)
- The largest positive number (right side)

So we compare both ends.

Approach

Algorithm Steps

Initialize:
- left = 0
- right = n - 1
- Create result array of size n
Fill result from end:
- Compare nums[left]^2 and nums[right]^2
- Place larger value at end
Move pointers accordingly:
- If left square is bigger -> left++
- Else -> right--

Code (Python)

def sortedSquares(nums):
    n = len(nums)
    result = [0] * n

    left = 0
    right = n - 1
    pos = n - 1

    while left <= right:
        if abs(nums[left]) > abs(nums[right]):
            result[pos] = nums[left] ** 2
            left += 1
        else:
            result[pos] = nums[right] ** 2
            right -= 1
        pos -= 1

    return result

Step-by-Step Explanation

For [-4, -1, 0, 3, 10]:

Compare |-4| and |10| -> 100
Compare |-4| and |3| -> 16
Compare |-1| and |3| -> 9
Continue…

Final -> [0, 1, 9, 16, 100]

Complexity Analysis

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

Conclusion

This problem demonstrates the power of the two-pointer technique for optimizing problems involving sorted arrays.

Guess the Number Higher or Lower

Sruthika Ramachandran — Sun, 22 Mar 2026 16:39:36 +0000

Introduction

This problem is based on a guessing game where we need to find a hidden number efficiently.

Instead of checking every number one by one, we can use Binary Search, which drastically reduces the number of guesses.

Problem Statement

You are given a number n. A number is picked between 1 and n.

You need to guess the number using the API:

guess(num)

It returns:

-1 -> Your guess is too high
1 -> Your guess is too low
0 -> Correct guess

Return the number that was picked.

Examples

Example 1:
Input: n = 10, pick = 6
Output: 6

Example 2:
Input: n = 1, pick = 1
Output: 1

Example 3:
Input: n = 2, pick = 1
Output: 1

Intuition

If guess is too high -> search left
If guess is too low -> search right

This perfectly fits Binary Search

Approach (Binary Search)

Algorithm Steps

Initialize:
- low = 1
- high = n
While low <= high:
- Find mid: mid = (low + high) // 2
- Call guess(mid):
  - If 0 → return mid
  - If -1 -> search left -> high = mid - 1
  - If 1 -> search right -> low = mid + 1

Code (Python)

def guessNumber(n):
    low = 1
    high = n

    while low <= high:
        mid = (low + high) // 2
        result = guess(mid)

        if result == 0:
            return mid
        elif result == -1:
            high = mid - 1
        else:
            low = mid + 1

Step-by-Step Explanation

For n = 10, pick = 6:

mid = 5 -> too low -> go right
mid = 8 -> too high -> go left
mid = 6 -> correct

Complexity Analysis

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

Conclusion

This problem demonstrates the power of Binary Search, which is one of the most important techniques in programming.

Merge Two Linked List

Sruthika Ramachandran — Sun, 22 Mar 2026 16:33:51 +0000

Introduction

Linked Lists are a fundamental data structure in computer science.
A common problem is merging two sorted linked lists into one sorted list.

This problem helps in understanding pointer manipulation and is frequently asked in interviews.

Problem Statement

You are given two sorted linked lists list1 and list2.

Task:
Merge them into a single sorted linked list and return its head.

Conditions:

Lists are already sorted
Merge should be done by rearranging nodes (not creating new list unnecessarily)

Examples

Example 1:
Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]

Example 2:
Input: list1 = [], list2 = []
Output: []

Example 3:
Input: list1 = [], list2 = [0]
Output: [0]

Intuition

Compare nodes from both lists
Pick the smaller value
Move forward

This is similar to the merge step in merge sort

Approach

We use a dummy node to simplify handling.

Algorithm Steps

Create a dummy node
Use a pointer current
Compare nodes from both lists:
- Attach smaller node to result
- Move that list forward
When one list ends:
- Attach remaining part of the other list
Return dummy.next

Code (Python)

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def mergeTwoLists(list1, list2):
    dummy = ListNode(-1)
    current = dummy

    while list1 and list2:
        if list1.val < list2.val:
            current.next = list1
            list1 = list1.next
        else:
            current.next = list2
            list2 = list2.next

        current = current.next

    # Attach remaining nodes
    if list1:
        current.next = list1
    else:
        current.next = list2

    return dummy.next

Step-by-Step Explanation

For:
[1 -> 2 -> 4] and [1 -> 3 -> 4]

Compare 1 and 1 -> pick one
Compare 2 and 1 -> pick 1
Compare 2 and 3 -> pick 2
Continue until done

Final = [1 -> 1 -> 2 -> 3 -> 4 -> 4]

Complexity Analysis

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

Conclusion

Merging two sorted linked lists is a fundamental problem that teaches efficient pointer handling and merging logic.

Valid Anagram

Sruthika Ramachandran — Sun, 22 Mar 2026 16:27:37 +0000

Introduction

Strings are one of the most important topics in programming.
A common problem is checking whether two strings are anagrams, which means they contain the same characters in a different order.

Problem Statement

Given two strings s and t, return:

true if t is an anagram of s
false otherwise

Note:

Both strings contain only lowercase English letters

Examples

Example 1:
Input: s = "anagram", t = "nagaram"
Output: true

Example 2:
Input: s = "rat", t = "car"
Output: false

Intuition

If two strings are anagrams:
- They must have the same characters
- With the same frequency

Approach (Frequency Count)

Instead of sorting, we count occurrences of each character.

Algorithm Steps

If lengths are different -> return false
Create a frequency array of size 26
Traverse both strings:
- Increment count for s[i]
- Decrement count for t[i]
If all values are 0 -> anagram

Code (Python)

def is_anagram(s, t):
    if len(s) != len(t):
        return False

    count = [0] * 26

    for i in range(len(s)):
        count[ord(s[i]) - ord('a')] += 1
        count[ord(t[i]) - ord('a')] -= 1

    return all(c == 0 for c in count)

Step-by-Step Explanation

For "anagram" and "nagaram":

Count characters in both strings
Each increment cancels with decrement
Final array -> all zeros -> valid anagram

Complexity Analysis

Time Complexity: O(n)
Space Complexity: O(1) (fixed 26 letters)

Conclusion

Checking for anagrams is a fundamental string problem that teaches frequency counting and efficient comparison techniques.

Move Zeores

Sruthika Ramachandran — Sun, 22 Mar 2026 16:21:25 +0000

Introduction

In array manipulation problems, we often need to rearrange elements while maintaining their order.

This problem focuses on moving all 0s to the end of the array while keeping the relative order of non-zero elements unchanged.

Problem Statement

Given an integer array nums, move all 0s to the end while maintaining the order of non-zero elements.

Constraints:

Perform the operation in-place
Do not create a copy of the array

Examples

Example 1:
Input: [0, 1, 0, 3, 12]
Output: [1, 3, 12, 0, 0]

Example 2:
Input: [0]
Output: [0]

Intuition

Move all non-zero elements forward
Fill remaining positions with 0s

This ensures:

Order is maintained
No extra space is used

Approach

We use a pointer j to track the position where the next non-zero element should go.

Algorithm Steps

Initialize j = 0
Traverse array using i:

If nums[i] != 0:
- Swap nums[i] with nums[j]
- Increment j

End result: all non-zero elements are shifted forward, zeros move to end

Code (Python)

def move_zeroes(nums):
    j = 0

    for i in range(len(nums)):
        if nums[i] != 0:
            nums[i], nums[j] = nums[j], nums[i]
            j += 1

Step-by-Step Explanation

For [0, 1, 0, 3, 12]:

Skip 0
Move 1 -> [1, 0, 0, 3, 12]
Skip 0
Move 3 -> [1, 3, 0, 0, 12]
Move 12 -> [1, 3, 12, 0, 0]

Complexity Analysis

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

Conclusion

The Move Zeroes problem is a great example of in-place array manipulation using two pointers.