DEV Community: Abivarsan R

Stop Writing O(n ) Loops — Master the Two Pointers Pattern

Abivarsan R — Sat, 06 Jun 2026 07:56:10 +0000

A hands-on guide to one of the most powerful algorithmic patterns you'll use every week — with real code in Java, Python, and C.

✍️ Written for developers who want to level up · ⏱ ~25 min read

The Loop That Was Silently Killing Your Code

Let me tell you a story I'm mildly embarrassed about. Early in my coding journey, I was given a classic problem: "Find two numbers in a sorted array that add up to a target." Simple enough, right? I wrote a nested loop — two for loops, one inside the other — and it worked. All test cases passed. I submitted. Green checkmarks. I felt like a genius.

Then my friend looked at my code and said, "Bro, your solution is O(n²). On an array of a million elements, that's a trillion operations." I stared at him blankly. He then showed me a version that did the same thing in O(n) — one single pass — using something called the Two Pointers pattern. It used eight lines of code. Mine used eighteen. His was a hundred times faster at scale. I felt significantly less genius.

The Two Pointers pattern is one of those ideas that, once you see it, you can't unsee it. You'll start recognising problems that scream for it. You'll look at nested loops and feel a twitch. It is not an exaggeration to say it will change how you think about array and string problems. Today, we're going deep — the intuition, the mechanics, the code in Java, Python, and C, the classic problems, the pitfalls, and a hands-on challenge to cement it all. Let's go.

What Is the Two Pointers Pattern?

Here is the best real-world analogy I've found. Imagine you're playing a game where you have a row of numbered tiles on the floor. You want to find two tiles whose values add to 10. The dumb way? Start at tile 1, check it against every other tile. Then start at tile 2, check against every other tile. That's the nested loop approach — exhaustive, boring, slow.

The smart way? You and your friend stand at opposite ends of the row. You call out the sum of your two tiles. If it's too high, your friend (at the right end) steps inward. If it's too low, you (at the left end) step inward. You both move toward each other based on the result, and you cover the entire search space in a single coordinated walk. That's Two Pointers.

Two Pointers is a technique where you maintain two index variables — typically called left and right — and move them strategically through a data structure to solve a problem in a single linear pass, eliminating the need for a nested loop.

There are actually three main flavours of Two Pointers. Understanding which variant to use is half the battle:

Variant 1 — Opposite Ends (Converging Pointers)

Both pointers start at the two ends of the array and move toward each other. Used when the array is sorted and you're looking for a pair with some property (sum, difference, etc.). This is the classic form.

Variant 2 — Same Direction (Sliding / Fast-Slow)

Both pointers start at the same end. One moves fast, the other moves slowly based on a condition. Used for removing duplicates, finding subarrays, or detecting cycles in linked lists.

Variant 3 — Two Arrays / Strings

One pointer in each of two separate arrays or strings, both moving forward. Used for merging, comparing, or intersecting sequences.

VARIANT 1 — CONVERGING (Opposite Ends)

Array:  [ 1,  3,  5,  7,  9, 11, 15 ]
         ↑                          ↑
        left                      right

  sum too small → move left  →
  sum too large → move right ←
  converge until they meet

VARIANT 2 — SAME DIRECTION (Fast + Slow)

Array:  [ 1,  1,  2,  3,  3,  4,  5 ]
         ↑
        slow
              ↑
             fast

  fast scans; slow marks the "write position"
  fast overtakes slow when it finds a unique value

VARIANT 3 — TWO ARRAYS

A: [ 1,  3,  5,  7 ]     B: [ 2,  3,  6,  8 ]
    ↑                         ↑
   pA                        pB

  advance the pointer pointing at the smaller value

How Does It Actually Work? The Core Mechanics

Let's anchor the intuition with the most foundational Two Pointers problem: the Two Sum II problem on a sorted array. Given a sorted array and a target, find the indices of two numbers that add up to the target.

Here's the step-by-step logic for the converging variant:

Set left = 0 (beginning of array), right = n - 1 (end of array).
Compute sum = array[left] + array[right].
If sum == target → you found it. Return the indices.
If sum < target → the sum is too small. To increase it, move left one step right (toward larger values).
If sum > target → the sum is too large. To decrease it, move right one step left (toward smaller values).
Repeat until left < right. If they cross without finding the pair, no pair exists.

Why does this work? Because the array is sorted, we have predictable directionality. When we say "move left to the right," we know for certain we're increasing the sum. When we move right to the left, we're decreasing it. Without sorting, this guarantee collapses and Two Pointers won't work in this form.

💡 Pro Tip: The Two Pointers technique works because the data has a monotonic property — either sorted order or a directional constraint. Before reaching for Two Pointers, always ask: "Is there an ordering I can exploit?" If yes, you probably have a Two Pointers problem.

The time complexity drops from O(n²) (brute force nested loops) to O(n) — because in the worst case, the two pointers together traverse the array exactly once. Space complexity is O(1) — no extra data structure needed, just two integer variables.

Approach	Time Complexity	Space Complexity
Brute Force (nested loops)	O(n²)	O(1)
Hash Map	O(n)	O(n)
Two Pointers (sorted)	O(n)	O(1)

Two Pointers is often the sweet spot — matching the speed of hash maps with the space efficiency of brute force.

Code Walkthroughs — Java, Python, and C

Let's implement the core Two Pointers problems in all three languages. We'll cover three problems progressively: Two Sum II, Remove Duplicates from Sorted Array, and Container With Most Water. Each one teaches a different dimension of the pattern.

Problem 1 — Two Sum II (Converging Pointers)

Given a sorted array of integers and a target, return the 1-based indices of the two numbers that add up to the target.

Python

def two_sum(numbers: list[int], target: int) -> list[int]:
    left = 0                        # start at the beginning
    right = len(numbers) - 1       # start at the end

    while left < right:             # loop until pointers meet
        current_sum = numbers[left] + numbers[right]

        if current_sum == target:
            # found! return 1-based indices as required
            return [left + 1, right + 1]

        elif current_sum < target:
            # sum is too small → need a larger left value
            left += 1

        else:
            # sum is too large → need a smaller right value
            right -= 1

    return []   # no pair found (problem guarantees one exists, but good practice)


# ── Test ──
numbers = [2, 7, 11, 15]
target = 9
print(two_sum(numbers, target))   # Output: [1, 2]  (2 + 7 = 9)

numbers2 = [1, 3, 4, 5, 7, 10, 11]
target2 = 9
print(two_sum(numbers2, target2)) # Output: [3, 4]
# left=0(1), right=6(11) → 12 > 9 → right--
# left=0(1), right=5(10) → 11 > 9 → right--
# left=0(1), right=4(7)  → 8 < 9  → left++
# left=1(3), right=4(7)  → 10 > 9 → right--
# left=1(3), right=3(5)  → 8 < 9  → left++
# left=2(4), right=3(5)  → 9 == 9 → return [3, 4] ✓

Java

public class TwoSum {

    public static int[] twoSum(int[] numbers, int target) {
        int left = 0;                    // pointer at the start
        int right = numbers.length - 1; // pointer at the end

        while (left < right) {
            int sum = numbers[left] + numbers[right];

            if (sum == target) {
                // return 1-based indices (problem requirement)
                return new int[]{left + 1, right + 1};
            } else if (sum < target) {
                left++;   // need bigger left value → move right
            } else {
                right--;  // need smaller right value → move left
            }
        }
        return new int[]{};  // no solution found
    }

    public static void main(String[] args) {
        int[] numbers = {2, 7, 11, 15};
        int[] result = twoSum(numbers, 9);
        System.out.println(result[0] + ", " + result[1]); // 1, 2

        int[] numbers2 = {1, 2, 3, 4, 4, 9, 56, 90};
        int[] result2 = twoSum(numbers2, 8);
        System.out.println(result2[0] + ", " + result2[1]); // 4, 5  (4+4=8)
    }
}

#include <stdio.h>
#include <stdlib.h>

/* two_sum: finds two indices (1-based) whose values sum to target.
   Writes result into out[0] and out[1]. Returns 1 on success, 0 on failure. */
int two_sum(int *numbers, int n, int target, int *out) {
    int left  = 0;       /* start pointer */
    int right = n - 1;   /* end pointer   */

    while (left < right) {
        int sum = numbers[left] + numbers[right];

        if (sum == target) {
            out[0] = left + 1;   /* convert to 1-based */
            out[1] = right + 1;
            return 1;            /* success */
        } else if (sum < target) {
            left++;              /* too small → move left pointer right */
        } else {
            right--;             /* too large → move right pointer left */
        }
    }
    return 0;   /* not found */
}

int main(void) {
    int numbers[] = {2, 7, 11, 15};
    int n = sizeof(numbers) / sizeof(numbers[0]);  /* compute length */
    int out[2];

    if (two_sum(numbers, n, 9, out)) {
        printf("Indices: %d, %d\n", out[0], out[1]); /* Indices: 1, 2 */
    }
    return 0;
}

Problem 2 — Remove Duplicates from Sorted Array (Same Direction)

Given a sorted array, remove duplicates in-place. Return the length of the new array. This is the fast/slow pointer variant — one pointer writes, one pointer reads.

Python

def remove_duplicates(nums: list[int]) -> int:
    if not nums:
        return 0

    # 'slow' marks the last position we wrote a unique value to
    slow = 0

    # 'fast' scans every element ahead
    for fast in range(1, len(nums)):
        if nums[fast] != nums[slow]:
            # found a new unique value — move slow forward and write it
            slow += 1
            nums[slow] = nums[fast]

    # slow is now the index of the last unique element
    # so the count of unique elements is slow + 1
    return slow + 1


# ── Test ──
nums = [1, 1, 2, 2, 3, 4, 4, 5]
k = remove_duplicates(nums)
print(k)            # 5
print(nums[:k])     # [1, 2, 3, 4, 5]

# Trace:
# fast=1: nums[1]=1 == nums[0]=1 → skip
# fast=2: nums[2]=2 != nums[0]=1 → slow=1, nums[1]=2
# fast=3: nums[3]=2 == nums[1]=2 → skip
# fast=4: nums[4]=3 != nums[1]=2 → slow=2, nums[2]=3
# fast=5: nums[5]=4 != nums[2]=3 → slow=3, nums[3]=4
# fast=6: nums[6]=4 == nums[3]=4 → skip
# fast=7: nums[7]=5 != nums[3]=4 → slow=4, nums[4]=5
# return slow+1 = 5 ✓

Java

public class RemoveDuplicates {

    public static int removeDuplicates(int[] nums) {
        if (nums.length == 0) return 0;

        int slow = 0;  // "write" pointer — tracks last unique element position

        for (int fast = 1; fast < nums.length; fast++) {
            // 'fast' is the "read" pointer — scans everything
            if (nums[fast] != nums[slow]) {
                slow++;               // advance write head
                nums[slow] = nums[fast];  // write the new unique value
            }
            // if equal, fast just keeps moving and slow stays put
        }

        return slow + 1;  // number of unique elements
    }

    public static void main(String[] args) {
        int[] nums = {0, 0, 1, 1, 1, 2, 2, 3, 3, 4};
        int k = removeDuplicates(nums);
        System.out.println("Unique count: " + k);  // 5
        // First k elements of nums are now: [0, 1, 2, 3, 4]
    }
}

#include <stdio.h>

/* remove_duplicates: modifies array in place.
   Returns the count of unique elements. */
int remove_duplicates(int *nums, int n) {
    if (n == 0) return 0;

    int slow = 0;   /* write pointer: last position of a confirmed unique value */

    for (int fast = 1; fast < n; fast++) {
        /* fast is the read pointer: advances every iteration */
        if (nums[fast] != nums[slow]) {
            slow++;
            nums[slow] = nums[fast];  /* overwrite with the new unique value */
        }
    }

    return slow + 1;  /* total unique elements */
}

int main(void) {
    int nums[] = {1, 1, 2, 3, 3, 4, 4, 5};
    int n = sizeof(nums) / sizeof(nums[0]);
    int k = remove_duplicates(nums, n);

    printf("Unique count: %d\n", k);    /* 5 */
    printf("Array: ");
    for (int i = 0; i < k; i++) {
        printf("%d ", nums[i]);         /* 1 2 3 4 5 */
    }
    printf("\n");
    return 0;
}

Problem 3 — Container With Most Water (Converging + Greedy Decision)

Given an array where each element represents a vertical line's height, find two lines that together with the x-axis form a container holding the most water. This is a brilliant problem because the Two Pointers move isn't arbitrary — it's driven by a greedy insight.

🔍 Fun Fact: The greedy insight: The area of water is constrained by the shorter line. If we move the pointer at the taller line inward, we can only shrink the width — so the area can only stay the same or decrease. But if we move the shorter line, there's a chance of finding a taller line that improves the area. So we always move the shorter pointer.

Python

def max_area(height: list[int]) -> int:
    left = 0
    right = len(height) - 1
    max_water = 0

    while left < right:
        # width = distance between the two lines
        width = right - left

        # height is limited by the shorter of the two lines
        current_height = min(height[left], height[right])

        # compute and update max area
        max_water = max(max_water, width * current_height)

        # greedy move: discard the shorter line by moving its pointer inward
        # rationale: keeping the shorter line can never improve the area
        if height[left] < height[right]:
            left += 1
        else:
            right -= 1

    return max_water


# ── Test ──
print(max_area([1, 8, 6, 2, 5, 4, 8, 3, 7]))  # 49
# The best container is between index 1 (height=8) and index 8 (height=7)
# width = 8-1 = 7, height = min(8,7) = 7, area = 49

Java

public class MaxWater {

    public static int maxArea(int[] height) {
        int left = 0;
        int right = height.length - 1;
        int maxWater = 0;

        while (left < right) {
            int width  = right - left;
            int h      = Math.min(height[left], height[right]);
            int area   = width * h;

            maxWater = Math.max(maxWater, area);

            // move the shorter wall's pointer inward
            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }

        return maxWater;
    }

    public static void main(String[] args) {
        int[] height = {1, 8, 6, 2, 5, 4, 8, 3, 7};
        System.out.println(maxArea(height));  // 49
    }
}

#include <stdio.h>

/* Helper macros */
#define MIN(a, b) ((a) < (b) ? (a) : (b))
#define MAX(a, b) ((a) > (b) ? (a) : (b))

int max_area(int *height, int n) {
    int left      = 0;
    int right     = n - 1;
    int max_water = 0;

    while (left < right) {
        int width = right - left;
        int h     = MIN(height[left], height[right]);
        int area  = width * h;

        max_water = MAX(max_water, area);

        /* always move the shorter wall inward */
        if (height[left] < height[right]) {
            left++;
        } else {
            right--;
        }
    }
    return max_water;
}

int main(void) {
    int height[] = {1, 8, 6, 2, 5, 4, 8, 3, 7};
    int n = sizeof(height) / sizeof(height[0]);
    printf("Max water: %d\n", max_area(height, n));  /* 49 */
    return 0;
}

Common Pitfalls (I've Hit Every Single One)

Pitfall 1 — Using Two Pointers on an Unsorted Array

The converging pointer technique only works on sorted arrays for sum/pair problems. When I first learned Two Pointers, I tried applying it to an unsorted array and got wrong answers I couldn't debug for hours. The core logic — "move left to increase the sum, move right to decrease it" — relies entirely on sorted order. If the array isn't sorted, sort it first (paying the O(n log n) cost), or switch to a hash map approach.

⚠️ Watch Out! Never assume the array is sorted just because it "looks" sorted in your test case. Always check or sort explicitly. One test case with a random array will expose the bug immediately.

Pitfall 2 — Off-by-One Errors with the Loop Condition

The loop condition while (left < right) vs while (left <= right) matters enormously. Using <= can cause you to use the same element twice (pairing an element with itself). For all two-element pair problems, use strict <. I've cost myself points in contests over this exact character.

Pitfall 3 — Moving Both Pointers When You Should Move One

When your sum equals the target, you've found your answer — return it, don't keep moving. But in related problems (like finding all pairs, or 3Sum), after finding a match you might move both pointers. The mistake is moving only one. When you find a valid pair and need to continue searching, move both: left++; right--; Otherwise you get duplicate results.

Pitfall 4 — Forgetting to Handle the Empty Array or Single Element

In C especially, accessing array[-1] or going out of bounds is undefined behaviour — it can corrupt memory silently and crash in the most confusing ways. Always check if (n == 0 || n == 1) return ... before initialising pointers. Python and Java throw exceptions; C just detonates quietly.

Pitfall 5 — Applying the Converging Pattern to the Wrong Problem Shape

Two Pointers is not always the right tool. If the problem involves a subarray or substring with no clear sorted property but a size constraint, you likely want a sliding window instead. Sliding window is Two Pointers' cousin — one pointer marks the start of a window, the other expands or contracts it. Two Pointers without sorting often becomes a sliding window problem in disguise.

💡 Pro Tip — Quick decision tree:

Sorted array + pair sum? → Converging Two Pointers

Subarray with running condition? → Sliding Window (fast/slow variant)

Merging two sorted arrays? → Two-array Two Pointers

Hands-On Challenge — Three Problems to Cement It

Reading about patterns is good. Writing them from scratch is what actually wires the pattern into your brain. Here are three problems in increasing difficulty. Try each one before looking at the solution.

Challenge 1 — Valid Palindrome (Easy)

Given a string, check if it is a palindrome considering only alphanumeric characters and ignoring case.

Input: "A man, a plan, a canal: Panama"

Output: true

Hint: Put one pointer at the start, one at the end. Skip non-alphanumeric characters. Compare characters (case-insensitive). If they ever differ, return false. If the pointers cross, return true.

Python — Solution

def is_palindrome(s: str) -> bool:
    left, right = 0, len(s) - 1

    while left < right:
        # skip non-alphanumeric from left
        while left < right and not s[left].isalnum():
            left += 1
        # skip non-alphanumeric from right
        while left < right and not s[right].isalnum():
            right -= 1

        # case-insensitive character comparison
        if s[left].lower() != s[right].lower():
            return False

        left += 1
        right -= 1

    return True

print(is_palindrome("A man, a plan, a canal: Panama"))  # True
print(is_palindrome("race a car"))                       # False

Challenge 2 — 3Sum (Medium)

Given an array of integers, find all unique triplets that sum to zero.

Input: [-1, 0, 1, 2, -1, -4]

Output: [[-1, -1, 2], [-1, 0, 1]]

Hint: Sort the array. Fix one element at index i using an outer loop. Then run Two Pointers (left = i+1, right = n-1) to find pairs that sum to -nums[i]. After finding a valid triplet, skip duplicates by moving pointers past equal values.

Python — Solution

def three_sum(nums: list[int]) -> list[list[int]]:
    nums.sort()          # crucial: sort first
    result = []

    for i in range(len(nums) - 2):
        # skip duplicate values for the fixed element
        if i > 0 and nums[i] == nums[i - 1]:
            continue

        left  = i + 1
        right = len(nums) - 1

        while left < right:
            total = nums[i] + nums[left] + nums[right]

            if total == 0:
                result.append([nums[i], nums[left], nums[right]])

                # skip duplicates on both sides
                while left < right and nums[left] == nums[left + 1]:
                    left += 1
                while left < right and nums[right] == nums[right - 1]:
                    right -= 1

                # move both pointers after recording the triplet
                left += 1
                right -= 1

            elif total < 0:
                left += 1   # need bigger value
            else:
                right -= 1  # need smaller value

    return result

print(three_sum([-1, 0, 1, 2, -1, -4]))  # [[-1, -1, 2], [-1, 0, 1]]

Challenge 3 — Trapping Rain Water (Hard)

Given an array where each element is the height of a bar, compute how much rainwater can be trapped between bars.

Input: [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]

Output: 6

Hint: Use Two Pointers with two running max values: left_max and right_max. At each step, process the side with the smaller max. Water at a position = max_height_on_that_side − current_height. This avoids needing prefix/suffix max arrays.

Python — Solution

def trap(height: list[int]) -> int:
    left, right = 0, len(height) - 1
    left_max = right_max = 0
    water = 0

    while left < right:
        if height[left] < height[right]:
            # process left side — right side is guaranteed taller
            if height[left] >= left_max:
                left_max = height[left]   # update max, no water trapped here
            else:
                water += left_max - height[left]   # water fills the gap
            left += 1
        else:
            # process right side — left side is guaranteed taller
            if height[right] >= right_max:
                right_max = height[right]
            else:
                water += right_max - height[right]
            right -= 1

    return water

print(trap([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]))  # 6

💡 Pro Tip: Trapping Rain Water is a classic interview question at top-tier companies. If you can implement this cleanly in an interview, you immediately signal strong algorithmic thinking. Practise explaining the why behind each pointer movement — that's what interviewers care about.

⚡ Recap — Key Takeaways

Two Pointers eliminates nested loops — drops O(n²) problems to O(n) time with O(1) space.
Three variants: converging (opposite ends), fast/slow (same direction), two-array (one pointer per sequence).
Sorted order is the prerequisite for converging pointers — always sort first if needed.
Move the pointer that can improve your answer — in sum problems, move toward more favourable values; in max-area problems, discard the shorter wall.
Loop condition is left < right (strict) to avoid pairing an element with itself.
Fast/slow pointers are perfect for in-place array modifications — slow writes, fast reads.
3Sum = outer loop + Two Pointers — this generalises to k-Sum problems.
Trapping Rain Water is the hardest Two Pointers application — master it and you've mastered the pattern.
Know when NOT to use it — unsorted + no ordering property → use hash map; running window condition → use sliding window.

What's Next? — Your Learning Path

Two Pointers is one node in a larger graph of algorithmic patterns. Here's where to go from here:

Immediate Next: Sliding Window

Sliding Window is the fast/slow variant taken to its full form. Problems: Longest Substring Without Repeating Characters, Minimum Size Subarray Sum, Longest Repeating Character Replacement. Once you know Two Pointers, Sliding Window is about a day's work to learn.

Then: Binary Search

Binary Search and Two Pointers are siblings — both exploit sorted order. Many problems can be solved with either, and knowing both lets you pick the more elegant solution. Practise on: Search in Rotated Sorted Array, Find Minimum in Rotated Sorted Array, Koko Eating Bananas.

Levelling Up: Linked List Two Pointers

The fast/slow pointer idea applies beautifully to linked lists — Floyd's Cycle Detection algorithm uses it to find cycles in O(1) space. Problems: Linked List Cycle, Find Middle of Linked List, Happy Number.

Problem Bank to Grind

Easy: Valid Palindrome, Move Zeroes, Squares of Sorted Array, Two Sum II
Medium: 3Sum, Container With Most Water, Remove Duplicates, Sort Colors (Dutch Flag)
Hard: Trapping Rain Water, 4Sum, Minimum Window Substring (sliding window)

Resources

LeetCode — search "Two Pointers" tag; filter by difficulty
NeetCode.io — free roadmap with Two Pointers section and video explanations
*"Introduction to Algorithms" * — Chapter on sorting gives you the sorted-array foundation
Grokking the Coding Interview — has a dedicated Two Pointers pattern chapter

"The best algorithm is the one you understand well enough to debug at 2 AM under interview pressure. Know the why behind every pointer move — not just the code."

We started from a nested loop embarrassment and arrived at trapping rainwater with a single linear pass. That's the journey of learning this pattern — from brute force to elegance, from O(n²) to O(n). Every problem you solve with Two Pointers builds the instinct to spot the next one faster. Go grind those LeetCode problems, share your solutions with the crew, and let me know when you get Trapping Rain Water on the first try. That's a milestone worth celebrating.

Happy coding. See you in the next one. 🚀

Written for developers who learn best by doing · Two Pointers Pattern · Java · Python · C

Share this with a friend who's still writing nested loops 😄

How I Solved N-Queens Using Bitmasking (Step-by-Step Guide)

Abivarsan R — Sun, 17 May 2026 15:35:28 +0000

🚀 Solving N-Queens Using Bitmasking (Step-by-Step Guide)

🧠 Problem Overview

The N-Queens problem:

Place n queens on an n × n chessboard such that no two queens attack each other.

⚡ Why Bitmasking?

Instead of using:

Sets ❌
Arrays ❌

We use:

Bits (0/1) ✅ → faster & efficient

🔥 Core Idea

We track:

cols → occupied columns
diag1 → main diagonals (↘)
diag2 → anti-diagonals (↙)

Each is stored as a binary number

🧩 Step-by-Step Explanation (VERY SIMPLE)

Let’s understand with n = 4

🔹 Step 1: Initial State

Row = 0
cols  = 0000
diag1 = 0000
diag2 = 0000

👉 All positions are free

🔹 Step 2: Find Available Positions

available = ~(cols | diag1 | diag2) & ((1 << n) - 1)

Result:

available = 1111

👉 All 4 columns are available

🔹 Step 3: Pick One Position

pos = available & -available

👉 Picks rightmost 1

pos = 0001  → column 0

🔹 Step 4: Place Queen

Board:

Q...
....
....
....

Update masks:

cols  = 0001
diag1 = 0010   (shift left)
diag2 = 0000   (shift right)

🔹 Step 5: Move to Next Row

Now row = 1

Find available:

available = ~(0001 | 0010 | 0000) = 1100

👉 Only column 2 and 3 are free

🔹 Step 6: Repeat Process

Pick:

pos = 0100  → column 2

Place queen:

Q...
..Q.
....
....

Update masks and continue…

🔹 Step 7: Dead End? Backtrack!

If no positions available:
👉 Go back (remove previous queen)
👉 Try next possibility

🔹 Step 8: When Row == n

All queens placed successfully 🎉

👉 Save board as a solution

💻 Final Bitmask Code

class Solution(object):
    def solveNQueens(self, n):
        result = []
        board = ["." * n for _ in range(n)]

        def backtrack(row, cols, diag1, diag2):
            if row == n:
                result.append(board[:])
                return

            available = ~(cols | diag1 | diag2) & ((1 << n) - 1)

            while available:
                pos = available & -available
                available = available & (available - 1)

                col = (pos.bit_length() - 1)

                board[row] = board[row][:col] + "Q" + board[row][col+1:]

                backtrack(
                    row + 1,
                    cols | pos,
                    (diag1 | pos) << 1,
                    (diag2 | pos) >> 1
                )

                board[row] = board[row][:col] + "." + board[row][col+1:]

        backtrack(0, 0, 0, 0)
        return result

⚡ Key Tricks Explained

✔ Get all safe positions

available = ~(cols | diag1 | diag2) & ((1 << n) - 1)

✔ Pick one position

pos = available & -available

✔ Remove used position

available = available & (available - 1)

⏱️ Complexity

Time: O(N!)
Space: O(N)

👉 But very fast in practice 🚀

🧠 Easy Memory Trick

👉 “Use bits to mark attacks, and pick positions using binary tricks”

💡 Interview Tip

Say this confidently:

“I optimized N-Queens using bitmasking to reduce constraint checking to constant time.”

🔥 That’s a standout answer

🚀 Final Thought

Bitmasking turns a normal backtracking solution into a high-performance algorithm.

Once you understand this, you unlock a new level of problem-solving 💡

🔖 Tags

Algorithms #Backtracking #Bitmasking #LeetCode #CodingInterview #DSA