DEV Community: Mubashir

Merging Sorted Linked List

Mubashir — Sun, 22 Mar 2026 16:20:22 +0000

In this task, I worked on merging two sorted linked lists into a single sorted linked list. This problem helped me understand how linked lists work and how to handle pointers efficiently.

What I Did:
I created a function mergeTwoLists that takes two sorted linked lists as input and merges them into one sorted list.
Example:
List1: 1 → 3 → 5

List2: 2 → 4 → 6

Output: 1 → 2 → 3 → 4 → 5 → 6
How I Solved It:
To solve this problem, I used a dummy node technique to simplify handling the head of the new list.
Step-by-step approach:
I created a dummy node to act as the starting point of the merged list
Used a pointer called tail to keep track of the last node in the merged list
Compared nodes from both lists:
If list1.val <= list2.val, I attached list1 node
Otherwise, I attached list2 node
Moved the pointer (tail) forward each time
Continued this until one list becomes empty
Final Step:
If any nodes are left in either list, I attached them directly to the end

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


class Solution:
    def mergeTwoLists(self, list1, list2):
        dummy = ListNode(-1)
        tail = dummy

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

            tail = tail.next

        # attach remaining nodes
        if list1:
            tail.next = list1
        else:
            tail.next = list2

        return dummy.next

Merge Sort For linked List

Mubashir — Sun, 22 Mar 2026 16:17:25 +0000

In this task, I worked on sorting a linked list using Merge Sort. Since
linked lists don’t allow random access like arrays, Merge Sort is one of the best sorting algorithms for them.

MY APPROACH
I created a function that takes the head of a linked list and returns a sorted linked list using merge sort.

EXAMPLE
INPUT : 4 -> 2 -> 1 -> 3 -> NULL
OUTPUT : 1-> 2-> 3-> 4

LOGIC IMPLEMENTED
I used the divide and conquer method.

Find the middle of the list using slow & fast pointers.
Split the list into two halves.
Recursively sort each half.
Merge both sorted lists.

How It Works

The list is repeatedly divided into halves.
Each half is sorted individually.
Then both halves are merged in sorted order.

class Solution:

    # Function to merge two sorted linked lists
    def merge(self, left, right):
        dummy = Node(0)
        tail = dummy

        while left and right:
            if left.data < right.data:
                tail.next = left
                left = left.next
            else:
                tail.next = right
                right = right.next
            tail = tail.next

        if left:
            tail.next = left
        if right:
            tail.next = right

        return dummy.next

    # Function to find middle of linked list
    def getMiddle(self, head):
        slow = head
        fast = head.next

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

        return slow

    # Main merge sort function
    def mergeSort(self, head):
        if not head or not head.next:
            return head

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

        # Step 2: Sort both halves
        left = self.mergeSort(head)
        right = self.mergeSort(next_to_mid)

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

        return sorted_list

Remove Duplictes in sorted Linked List

Mubashir — Sun, 22 Mar 2026 15:34:27 +0000

In this task, I worked on removing duplicate nodes from a sorted linked list.
Since the list is already sorted, duplicate elements will always be next to each other, which makes the problem easier.

MY APPROACH
I created a function that takes the head of a sorted linked list and removes all duplicate nodes, returning the updated list

EXAMPLE
INPUT : 1->1->2->3->4->Null
output : 1->2->3->4

LOGIC IMPLEMENTED
Since the list is sorted:

I compared each node with its next node
If both values are the same → remove the duplicate
Otherwise → move to the next node

class Solution:
    def removeDuplicates(self, 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:

Since duplicates are adjacent, we only need to check the next node
If duplicate is found, we skip it by changing pointers
This removes duplicates without creating a new list

Reverse A List

Mubashir — Sun, 22 Mar 2026 14:03:15 +0000

In this task, I worked on reversing a singly linked list. Instead of creating a new list, I reversed it in-place by changing the links between nodes.

MY APPROACH
I created a function that takes the head of a linked list and returns the reversed linked list.

EXAMPLE
Input : 1 -> 2-> 3-> 4-> 5-> NULL
Output : 5-> 4-> 3-> 2-> 1

LOGIC IMPLEMENTED
To reverse the linked list, I used an iterative approach with three pointers:
prev -> keeps track of previous node
curr -> current node
next -> stores next node temporarily

Initialize: prev = None curr = head
Traverse the list:
- Store next node
- Reverse the link
Move pointers forward

class Solution:
    def reverseList(self, head):
        prev = None
        curr = head

        while curr:
            next_node = curr.next   # store next
            curr.next = prev        # reverse link
            prev = curr             # move prev
            curr = next_node        # move curr

        return prev

Majority Element

Mubashir — Sun, 22 Mar 2026 13:53:18 +0000

In this task, I worked on finding the majority element in an array.
A majority element is the element that appears more than n/2 times in the array.

MY APPROACH
I created a function that takes an array and returns the majority element, if it exists

EXAMPLE
arr = [2, 2, 1, 2, 3, 2, 2]
output : 2

LOGIC IMPLEMENTED
To solve this efficiently, I used Moore’s Voting Algorithm. Instead of counting every element, this algorithm helps find the majority element in one pass.

Keep a candidate and a count
Traverse the array:
If count = 0 -> update candidate
If element == candidate -> increase count
Else -> decrease count

class Solution:
    def majorityElement(self, arr):
        count = 0
        candidate = None
        for num in arr:
            if count == 0:
                candidate = num
            if num == candidate:
                count += 1
            else:
                count -= 1
        if arr.count(candidate) > len(arr) // 2:
            return candidate
        else:
            return -1

Search In Rotated Sorted Array

Mubashir — Sun, 22 Mar 2026 12:42:39 +0000

In this task, I worked on searching for a target element in a rotated sorted array.
A rotated array means a sorted array is shifted at some pivot point.

MY APPROACH
created a function that takes:

A rotated sorted array
A target value And returns the index of the target, or -1 if not found

LOGIC IMPLEMENTED
Instead of using normal search, I used a modified Binary Search. Even though the array is rotated, one half is always sorted.

Find the middle element
Check which half is sorted: Left half sorted OR right half sorted
Check if target lies in that sorted half
Adjust search range accordingly

EXAMPLE
Input :nums = [4,5,6,7,0,1,2], target = 0
output : 4

class Solution:
    def search(self, nums, target):
        low = 0
        high = 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

First And Last Occurence

Mubashir — Sun, 22 Mar 2026 12:34:08 +0000

In this task, I worked on finding the first and last positions of a given element in a sorted array.
Instead of scanning the entire array, I used a more efficient approach using Binary Search.

MY APPROACH
I created a function that takes:

A sorted array
A target element x

And returns:

The first occurrence index
The last occurrence index

EXAMPLE
Input : arr = [1, 2, 2, 2, 3, 4]
x = 2
output : [1,3]

HOW I SOLVED IT
To solve this effectively i used binary search twice,

To Find the first occurences, If element matches:
Store index
Move left to find earlier occurrence
To find the last occurences , If element matches:
Store index
Move left to find earlier occurrence

HOW IT WORKS
Binary search reduces the search space by half each time

For first occurrence -> we keep moving left
For last occurrence -> we keep moving right This ensures we find the exact boundaries

class Solution:
    def firstAndLast(self, arr, x):
        def findFirst(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
                elif arr[mid] < x:
                    low = mid + 1
                else:
                    high = mid - 1

            return first

        def findLast(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
                elif arr[mid] < x:
                    low = mid + 1
                else:
                    high = mid - 1

            return last

        return [findFirst(arr, x), findLast(arr, x)]

Squares Of Sorted Array

Mubashir — Sun, 22 Mar 2026 11:57:35 +0000

In this task, I worked on converting a sorted array into another sorted array of their squares.
Even though the input array is sorted, squaring the numbers can disturb the order (because of negative numbers). So we need a smart way to keep the result sorted.

MY APPROACH
I created a function that takes a sorted array and returns a new array containing the squares of each number in sorted order.

EXAMPLE
Input : nums = [-4, -1, 0, 3, 10]
output : [0,1,9,16,100]

LOGIC IMPLEMENTED
Instead of squaring and sorting again, I used a two-pointer approach:

One pointer at the start
One pointer at the end
Initialize:
left = 0
right = n-1
Create a result array
Compare:
Square of left element
Square of right element Place the larger square at the end and move pointers

class Solution:
    def sortedSquares(self, nums):
        n = len(nums)
        result = [0] * n

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

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

            pos -= 1

        return result

Guess Number Higher or Lower

Mubashir — Sun, 22 Mar 2026 11:16:41 +0000

In this task, I worked on guessing a number using a smart approach instead of checking every number one by one.

MY APPROACH
I created a function to guess a number between 1 and n using an API called guess(num).

The API returns:
-1 → my guess is higher than the picked number

1 → my guess is lower than the picked number
0 → my guess is correct

EXAMPLE :
Input : n = 10
pick = 6
output : 6

LOGIC IMPLEMENTED
Instead of checking all numbers, I used Binary Search:

Start from the middle
Initialize:
low = 1
high = n
While low <= high:
Find mid
Call guess(mid)
Adjust search range accordingly

class Solution:
    def guessNumber(self, n):
        low = 1
        high = n

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

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

Valid Anagram

Mubashir — Sun, 22 Mar 2026 11:05:33 +0000

OVERVIEW
In this task, I worked on checking whether two strings are anagrams of each other.
It means that both strings contain the same characters with the same frequency, just arranged differently.

MY APPROACH
I created a function that takes two strings s and t, and returns True if they are anagrams, otherwise False.

EXAMPLE
INPUT : s = "anagram"
t = "nagaram"
OUTPUT : TRUE

LOGIC IMPLEMENTED

Sort both strings
Compare them If both sorted strings are equal, they are anagrams.

HOW THE PROGRAM WORKS

Sorting arranges characters in order
If both strings have same characters, sorted results will match

class Solution:
    def isAnagram(self, s, t):
        return sorted(s) == sorted(t)

Move Zeros

Mubashir — Sun, 22 Mar 2026 10:46:58 +0000

OVERVIEW
In this task, I worked on moving all the zeroes in an array to the end while maintaining the order of non-zero elements.

WHAT I DID
I created a function that rearranges the array such that:

All non-zero elements stay in the front
All zeroes move to the end
The relative order remains the same

EXAMPLE
Input : nums = [0, 1, 0, 3, 12]
output : [1, 3, 12, 0, 0]

LOGIC IMPLEMENTED
To solve this problem, I used a two-pointer approach:

One pointer (pos) keeps track of where to place the next non-zero element
The other pointer (i) traverses the array
Traverse the array
If element is non-zero:
Swap it with position pos
Move pos forward

HOW IT WORKS

First, all non-zero elements are shifted to the front
While doing that, zeroes automatically move to the end
The order of non-zero elements is preserved

class Solution:
    def moveZeroes(self, nums):
        pos = 0  # position for next non-zero element

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

Next Permutation

Mubashir — Sun, 22 Mar 2026 10:36:00 +0000

In this task, I worked on finding the next lexicographically greater permutation of a given array. If such a permutation is not possible, we rearrange it to the smallest possible order (ascending).

WHAT I DID
I created a function that modifies the array to its next permutation in-place.

EXAMPLE
Input : arr[1,2,3]
ouput : [2,1,3],[1,3,2]

LOGIC IMPLEMENTED
Find index i such that:
nums[i] < nums[i+1]

Find index j such that:
nums[j] > nums[i]

Swap nums[i] and nums[j]
Reverse elements from i+1 to end

HOW IT WORKS

The algorithm finds the first place where order breaks from the right
Then it swaps with the next larger number
Finally, it rearranges the remaining elements to get the smallest possible order

class Solution:
    def nextPermutation(self, nums):
        n = len(nums)
        i = n - 2

        # Step 1: find first decreasing element
        while i >= 0 and nums[i] >= nums[i + 1]:
            i -= 1

        if i >= 0:
            j = n - 1

            # Step 2: find element just greater than nums[i]
            while nums[j] <= nums[i]:
                j -= 1

            # Step 3: swap
            nums[i], nums[j] = nums[j], nums[i]

        # Step 4: reverse the remaining array
        left, right = i + 1, n - 1
        while left < right:
            nums[left], nums[right] = nums[right], nums[left]
            left += 1
            right -= 1

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