DEV Community: Sachin Yadav

Bag of Tokens (Greedy Two Pointer Technique)

Sachin Yadav — Sun, 01 Feb 2026 16:46:02 +0000

The approach I used here is greedy I always want my score to increase so I will always go with the first condition that is if the power is greater than the current token then increment the count also if there is need or my power is less than the current token then I will always want to increase my power with the biggest token number. Therefore this gives the intuition that we need to sort the array of tokens in the ascending order so that when I am increasing my score then I pick from the left because it will be less than my power and if I want to increase my power then I will always choose from the right

/**
 * @param {number[]} tokens
 * @param {number} power
 * @return {number}
 */
var bagOfTokensScore = function (tokens, power) {
    tokens.sort((a, b) => a - b)
    let score = 0
    let maxScore = 0
    let i = 0
    let j = tokens.length - 1
    while (i <= j) {
        if (power >= tokens[i]) {
            power -= tokens[i]
            score++
            i++
            maxScore = Math.max(score, maxScore)
        } else if (score >= 1) {
            power = power + tokens[j]
            j--
            score--
        } else {
            return maxScore
        }
    }
    return maxScore
};

Leetcode 2705. Compact Object

Sachin Yadav — Sat, 27 Sep 2025 11:26:25 +0000

View the dry run live here https://leetcode-compact-object.netlify.app/

/**
 * @param {Object|Array} obj
 * @return {Object|Array}
 */
var compactObject = function (obj) {
    if (typeof obj !== 'object' || obj == null) {
        return obj
    }
    const isArray = Array.isArray(obj)
    const result = Array.isArray(obj) ? [] : {}
    const keys = Object.keys(obj)
    for (const key of keys) {
        let value = obj[key]
        let compactedValue = compactObject(value)
        if (Boolean(compactedValue)) {
            if (isArray) {
                result.push(compactedValue)
            } else {
                result[key] = compactedValue
            }
        }
    }
    return result
};

Leetcode 1493 Longest Subarray of 1's After Deleting One Element

Sachin Yadav — Sun, 24 Aug 2025 18:29:30 +0000

This problem is based on the sliding window technique.

Trick To Solve :- Instead of looking at this problem like deleting one element, this problem can actually be viewed as solving the longest subarray of 1 having at most one zero.

Solve using the at most one zero approach and then return maxLen-1 and not maxLen because you have solved for at most one zero.

One benefit of solving this problem is that, The exact same to same code can be used for another leetcode problem named Max Consecutive Ones III.

Please note in Max Consecutive Ones III we don't return maxLen-1 rather we return maxLen.

/**
 * @param {number[]} nums
 * @return {number}
 */
var longestSubarray = function (nums) {
    let i = 0
    let j = 0
    let n = nums.length
    let maxLen = 0
    let zeroCount = 0
    while (j < n) {
        let num = nums[j]
        if (num == 0) {
            zeroCount++
        }
        while (zeroCount > 1) {
            if (nums[i] == 0) {
                zeroCount--
            }
            i++
        }
        maxLen = Math.max(maxLen, j - i + 1)
        j++
    }
    return maxLen - 1
};

Leetcode 1493 Longest Subarray of 1's After Deleting One Element

Sachin Yadav — Sun, 24 Aug 2025 18:29:30 +0000

This problem is based on the sliding window technique.

Trick To Solve :- Instead of looking at this problem like deleting one element, this problem can actually be viewed as solving the longest subarray of 1 having at most one zero.

Solve using the at most one zero approach and then return maxLen-1 and not maxLen because you have solved for at most one zero.

One benefit of solving this problem is that, The exact same to same code can be used for another leetcode problem named Max Consecutive Ones III.

Please note in Max Consecutive Ones III we don't return maxLen-1 rather we return maxLen.

/**
 * @param {number[]} nums
 * @return {number}
 */
var longestSubarray = function (nums) {
    let i = 0
    let j = 0
    let n = nums.length
    let maxLen = 0
    let zeroCount = 0
    while (j < n) {
        let num = nums[j]
        if (num == 0) {
            zeroCount++
        }
        while (zeroCount > 1) {
            if (nums[i] == 0) {
                zeroCount--
            }
            i++
        }
        maxLen = Math.max(maxLen, j - i + 1)
        j++
    }
    return maxLen - 1
};

Leetcode 678 :- Valid Parenthesis String

Sachin Yadav — Thu, 19 Sep 2024 08:51:56 +0000

Today I solved the question LC 678 Valid Parenthesis String

Intuition

Since we have 3 choices to make for when we encounter a * we can solve this recursively.

Approach

Since the recursive solution would lead to a TLE for when s="**********************" therefore we can optimize the recursive calls using Dynamic Programming

Complexity

Time complexity: For the recursive code :- At the worst possible scenario we are making 3 branches when we encounter an * so the TC is 3^n

Code

//👇👇 Recursive Code
 var checkValidString = function (s, index = 0, count = 0) {
     if (count < 0) return false
     if (index === s.length) {
         return count === 0
     }
     if (s[index] === '(') {
         return checkValidString(s, index + 1, count + 1)
     } else if (s[index] === ')') {
         return checkValidString(s, index + 1, count - 1)
     } else {
         return checkValidString(s, index + 1, count + 1) || checkValidString(s, index + 1, count - 1) || checkValidString(s, index + 1, count)
     }
 };

// 👇👇DP Code
var checkValidString = function (s, index = 0, count = 0, memo = {}) {
    if (count < 0) return false;
    if (index === s.length) {
        return count === 0;
    }
    // Create a unique key for the current state
    const key = `${index},${count}`;
    if (key in memo) {
        return memo[key]; // Return cached result
    }
    let result;
    if (s[index] === '(') {
        result = checkValidString(s, index + 1, count + 1, memo);
    } else if (s[index] === ')') {
        result = checkValidString(s, index + 1, count - 1, memo);
    } else { // s[index] === '*'
        result = checkValidString(s, index + 1, count + 1, memo) || // Treat '*' as '('
                 checkValidString(s, index + 1, count - 1, memo) || // Treat '*' as ')'
                 checkValidString(s, index + 1, count, memo);       // Treat '*' as empty
    }
    memo[key] = result; // Store the result in the cache
    return result;
};