DEV Community: MD ARIFUL HAQUE

3551. Minimum Swaps to Sort by Digit Sum

MD ARIFUL HAQUE — Sat, 17 Oct 2026 19:42:10 +0000

3551. Minimum Swaps to Sort by Digit Sum

Difficulty: Medium

Topics: Senior, Array, Hash Table, Sorting, Weekly Contest 450

You are given an array nums of distinct positive integers. You need to sort the array in increasing order based on the sum of the digits of each number. If two numbers have the same digit sum, the smaller number appears first in the sorted order.

Return the minimum number of swaps required to rearrange nums into this sorted order.

A swap is defined as exchanging the values at two distinct positions in the array.

Example 1:

Input: nums = [37,100]
Output: 1
Explanation:
- Compute the digit sum for each integer: [3 + 7 = 10, 1 + 0 + 0 = 1] → [10, 1]
- Sort the integers based on digit sum: [100, 37]. Swap 37 with 100 to obtain the sorted order.
- Thus, the minimum number of swaps required to rearrange nums is 1.

Example 2:

Input: nums = [22,14,33,7]
Output: 0
Explanation:
- Compute the digit sum for each integer: [2 + 2 = 4, 1 + 4 = 5, 3 + 3 = 6, 7 = 7] → [4, 5, 6, 7]
- Sort the integers based on digit sum: [22, 14, 33, 7]. The array is already sorted.
- Thus, the minimum number of swaps required to rearrange nums is 0.

Example 3:

Input: nums = [18,43,34,16]
Output: 2
Explanation:
- Compute the digit sum for each integer: [1 + 8 = 9, 4 + 3 = 7, 3 + 4 = 7, 1 + 6 = 7] → [9, 7, 7, 7]
- Sort the integers based on digit sum: [16, 34, 43, 18]. Swap 18 with 16, and swap 43 with 34 to obtain the sorted order.
- Thus, the minimum number of swaps required to rearrange nums is 2.

Example 4:

Input: nums = [1]
Output: 0

Example 5:

Input: nums = [5,3,1]
Output: 1

Example 6:

Input: nums = [10,1]
Output: 1

Example 7:

Input: nums = [1000000000,1]
Output: 1

Example 8:

Input: nums = [9,8,7,6,5,4,3,2,1]
Output: 4

Example 9:

Input: nums = [11,20,2]
Output: 1

Example 10:

Input: nums = [100,10,1]
Output: 1

Constraints:

1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁹
nums consists of distinct positive integers.

Hint:

First, sort the array based on digit sum (and value as a tiebreaker). Then, map each original value to its index in the sorted array.
Now, the problem reduces to finding the minimum number of swaps to sort this mapped array. The answer is n - number_of_cycles in the permutation.

Solution:

We solve this problem by first determining the target sorted order (by digit sum, tie-broken by value), then reducing the problem to "minimum swaps to sort a permutation." Using the classic cycle-decomposition technique, the answer is n - number_of_cycles. The provided PHP implementation is correct and optimal.

Approach

Compute target order: For each number, calculate its digit sum and sort the array by (digit_sum, value) to obtain the desired final arrangement.
Map values to target positions: Since all numbers are distinct, build a hash map value → target_index.
Build the permutation array: For each position i in the original array, perm[i] = the index in the sorted array where nums[i] belongs.
Count cycles in the permutation: Traverse the permutation using a visited array; every unvisited node starts a new cycle.
Apply the formula: Minimum swaps = n − number_of_cycles.

Let's implement this solution in PHP: 3551. Minimum Swaps to Sort by Digit Sum

<?php
/**
 * Compute the sum of digits of a positive integer
 *
 * @param int $num
 * @return int
 */
function digitSum(int $num): int {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

/**
 * @param Integer[] $nums
 * @return Integer
 */
function minSwaps(array $nums): int {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
echo minSwaps([37,100]) .  "\n";                        // Output: 1
echo minSwaps([22,14,33,7]) .  "\n";                    // Output: 0
echo minSwaps([18,43,34,16]) .  "\n";                   // Output: 2
echo minSwaps([1]) .  "\n";                             // Output: 0
echo minSwaps([5, 3, 1]) .  "\n";                       // Output: 1
echo minSwaps([10, 1]) .  "\n";                         // Output: 1
echo minSwaps([1000000000, 1]) .  "\n";                 // Output: 1
echo minSwaps([9, 8, 7, 6, 5, 4, 3, 2, 1]) .  "\n";     // Output: 4
echo minSwaps([11, 20, 2]) .  "\n";                     // Output: 1
echo minSwaps([100, 10, 1]) .  "\n";                    // Output: 1
?>

Explanation:

Why cycle decomposition works:
- A permutation decomposes into disjoint cycles.
- A cycle of length k requires exactly k − 1 swaps to resolve.
- Summing over all cycles gives (k₁−1) + (k₂−1) + … = n − c, where c is the cycle count.
Digit sum computation:
- Repeatedly take num % 10 and divide by 10 — O(digits) per number.
Sorting tiebreaker:
- When digit sums match, the smaller number must come first (e.g., 16 < 34 < 43 in Example 3).
Distinctness of values:
- Guaranteed by the constraints, so a value → index map is safe and uniquely defined.
Traversal correctness:
- Following j = perm[j] from any node visits exactly its cycle before returning to the start, so marking visited[j] = true is sound.
Early exit:
- Arrays of length 0 or 1 need zero swaps (handled by the n <= 1 guard).

Complexity Analysis

Time: O(n log n)
- Digit sum computation: O(n · log₁₀(max)) ≈ O(n)
- Sorting: O(n log n)
- Building maps + permutation + cycle counting: O(n)
Space: O(n)
- $pairs, $valueToTargetIndex, $perm, $visited each use O(n) extra space.

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!

If you want more helpful content like this, feel free to follow me:

LinkedIn
GitHub

SellerMate BD: Local AI Product Copy for Bangladeshi Sellers

MD ARIFUL HAQUE — Sat, 17 Oct 2026 18:24:41 +0000

SellerMate BD: Local AI Product Copy for Bangladeshi Sellers

This is a submission for the Hacktoberfest Open-Source AI Challenge Week 2: Side Hustle.

What I Built

SellerMate BD is a local AI content assistant for small online sellers in Bangladesh. Sellers enter a product name, specifications, and warranty information, then generate product descriptions, key features, SEO metadata, Facebook captions, or FAQs in Bangla, English, or both.

The problem it addresses is the time and effort required to write clear product listings, especially for independent sellers who may not have a copywriter or a budget for hosted AI services. These are the customers I built it for; I haven't yet validated demand, pricing, or willingness to pay.

Demo

There isn't a publicly deployed demo yet. The app can be run locally with Docker Compose; setup instructions are in the README. A browser recording showing synthetic data being typed, generated with local Ollama, and saved is available in sellermate-bd.

The video is a local file, not a public URL; upload it to a video host before submitting if the challenge requires an accessible demo link.

Code

GitHub repository: sellermate-bd

I couldn't identify a public repository URL for this project from the available workspace details.

One important implementation choice is the prompt's instruction to use only seller-provided facts and not invent product claims.

How I Built It

SellerMate BD uses PHP 8.4 and Apache for the web app, SQLite for local draft history, and Ollama for local model inference. The default model is qwen2.5:3b, configurable through OLLAMA_MODEL.

The app supports Bangla and English content, saves generated drafts locally, and exports them as CSV. It also includes basic tests for input validation, prompt construction, output escaping, and parsing a sample product listing.

Generated content still needs human review. This MVP has no authentication or multi-tenant isolation, so it is intended to run locally and should not be exposed directly to the public internet.

Why Does Open Innovation Matter?

Local inference gives sellers an alternative to sending product details to a hosted AI API. It avoids per-request model API charges and makes it possible to inspect and adapt the model and prompts, including experimenting with Bangla product copy.

That doesn't make AI free: users still need suitable hardware, and model licenses and terms need to be checked, especially for commercial use.

Prize Categories

I'm not entering a partner category because the project doesn't currently use a listed partner's technology.

2916. Subarrays Distinct Element Sum of Squares II

MD ARIFUL HAQUE — Fri, 16 Oct 2026 17:48:26 +0000

2916. Subarrays Distinct Element Sum of Squares II

Difficulty: Hard

Topics: Principal, Array, Hash Table, Binary Indexed Tree, Segment Tree, Biweekly Contest 116

You are given a 0-indexed integer array nums.

The distinct count of a subarray of nums is defined as:

Let nums[i..j] be a subarray of nums consisting of all the indices from i to j such that 0 <= i <= j < nums.length. Then the number of distinct values in nums[i..j] is called the distinct count of nums[i..j].

Return the sum of the squares of distinct counts of all subarrays of nums.

Since the answer may be very large, return it modulo 10⁹ + 7.

A subarray is a contiguous non-empty sequence of elements within an array.

Example 1:

Input: nums = [1,2,1]
Output: 15
Explanation:
- Six possible subarrays are:
  - [1]: 1 distinct value
  - [2]: 1 distinct value
  - [1]: 1 distinct value
  - [1,2]: 2 distinct values
  - [2,1]: 2 distinct values
  - [1,2,1]: 2 distinct values
- The sum of the squares of the distinct counts in all subarrays is equal to 1² + 1² + 1² + 2² + 2² + 2² = 15.

Example 2:

Input: nums = [2,2]
Output: 3
Explanation:
- Three possible subarrays are:
  - [2]: 1 distinct value
  - [2]: 1 distinct value
  - [2,2]: 1 distinct value
- The sum of the squares of the distinct counts in all subarrays is equal to 12 + 12 + 12 = 3.

Example 3:

Input: nums = [1]
Output: 1

Example 4:

Input: nums = [1,2,3]
Output: 20

Example 5:

Input: nums = [1,1,1]
Output: 6

Example 7:

Input: nums = [1,2,1,2]
Output: 28

Example 8:

Input: nums = [2,2,2,2]
Output: 10

Constraints:

1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁵

Hint:

Consider the sum of the count of distinct values of subarrays ending with index i, let’s call it sum. Now if you need the sum of all subarrays ending with index i + 1 think how it can be related to sum and what extra will be needed to add to this.
You can find that extra sum using the segment tree.

Solution:

We scan the array by right endpoint i and maintain a segment tree over all possible left endpoints j. For each j, the tree stores the distinct count of nums[j..i]. When a new element nums[i] = x appears, only left endpoints after the previous occurrence of x gain one new distinct value, so we range-add +1 on [last[x] + 1, i]. The segment tree maintains both sum and sum of squares, so after each update the root’s square-sum gives the total for all subarrays ending at i. We accumulate this modulo 1e9 + 7.

Approach

Let last[x] be the previous index where x appeared before the current index.
For a fixed right endpoint i, define f(j) as the distinct count of nums[j..i].
When processing nums[i] = x:
- If x did not appear in nums[j..i-1], then f(j) increases by 1.
- This happens exactly when j > last[x].
- So we range-add +1 to all left endpoints in [last[x] + 1, i].
Maintain these values in a lazy segment tree.
Each node stores:
- sum: sum of values in its segment.
- sq: sum of squares of values in its segment.
- lazy: pending range addition.
After each range update, sq[1] is the sum of squares of distinct counts of all subarrays ending at i.
Add sq[1] to the answer modulo 1e9 + 7.
Update last[x] = i.

Let's implement this solution in PHP: 2916. Subarrays Distinct Element Sum of Squares II

<?php
/**
 * @param $sum
 * @param $sq
 * @param $lazy
 * @param $node
 * @param $l
 * @param $r
 * @param $val
 * @return void
 */
function apply(&$sum, &$sq, &$lazy, $node, $l, $r, $val)
{
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

/**
 * @param $sum
 * @param $sq
 * @param $lazy
 * @param $node
 * @param $l
 * @param $r
 * @return void
 */
function push(&$sum, &$sq, &$lazy, $node, $l, $r)
{
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

/**
 * @param $sum
 * @param $sq
 * @param $lazy
 * @param $node
 * @param $l
 * @param $r
 * @param $ql
 * @param $qr
 * @param $val
 * @return void
 */
function rangeAdd(
    &$sum,
    &$sq,
    &$lazy,
    $node,
    $l,
    $r,
    $ql,
    $qr,
    $val
) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

/**
 * @param Integer[] $nums
 * @return Integer
 */
function sumCounts(array $nums): int
{
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
echo sumCounts([1,2,1]) .  "\n";        // Output: 15
echo sumCounts([2,2]) .  "\n";          // Output: 3
echo sumCounts([1]) .  "\n";            // Output: 1
echo sumCounts([1,2,3]) .  "\n";        // Output: 20
echo sumCounts([1,1,1]) .  "\n";        // Output: 6
echo sumCounts([1,2,1,2]) .  "\n";      // Output: 28
echo sumCounts([2,2,2,2]) .  "\n";      // Output: 10
?>

Explanation:

A range addition of val to a segment changes each value a into a + val.
Therefore:
- New sum = old sum + len * val
- New sq = old sq + 2 * old sum * val + len * val * val
The segment tree propagates lazy additions to children only when needed.
Leaves with index greater than the current right endpoint remain 0, so the root effectively covers only valid subarrays ending at the current index.
The final answer is the sum over all right endpoints of the squared distinct counts of all subarrays ending there.

Complexity Analysis

Time Complexity: O(n log n)
- Each element causes one range update, costing O(log n).
- Root query after each update is O(1).
Space Complexity: O(n)
- Segment tree arrays use O(4n).
- The last hash map stores at most n entries.

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!

If you want more helpful content like this, feel free to follow me:

LinkedIn
GitHub

2913. Subarrays Distinct Element Sum of Squares I

MD ARIFUL HAQUE — Thu, 15 Oct 2026 16:53:33 +0000

2913. Subarrays Distinct Element Sum of Squares I

Difficulty: Easy

Topics: Mid Level, Array, Hash Table, Binary Indexed Tree, Segment Tree, Biweekly Contest 116

You are given a 0-indexed integer array nums.

The distinct count of a subarray of nums is defined as:

Let nums[i..j] be a subarray of nums consisting of all the indices from i to j such that 0 <= i <= j < nums.length. Then the number of distinct values in nums[i..j] is called the distinct count of nums[i..j].

Return the sum of the squares of distinct counts of all subarrays of nums.

A subarray is a contiguous non-empty sequence of elements within an array.

Example 1:

Input: nums = [1,2,1]
Output: 15
Explanation:
- Six possible subarrays are:
- [1]: 1 distinct value
- [2]: 1 distinct value
- [1]: 1 distinct value
- [1,2]: 2 distinct values
- [2,1]: 2 distinct values
- [1,2,1]: 2 distinct values
- The sum of the squares of the distinct counts in all subarrays is equal to 1² + 1² + 1² + 2² + 2² + 2² = 15.

Example 2:

Input: nums = [1,1]
Output: 3
Explanation:
- Three possible subarrays are:
- [1]: 1 distinct value
- [1]: 1 distinct value
- [1,1]: 1 distinct value
- The sum of the squares of the distinct counts in all subarrays is equal to 1² + 1² + 1² = 3.

Example 3:

Input: nums = [1]
Output: 1

Example 4:

Input: nums = [1,1,1]
Output: 6

Example 5:

Input: nums = [1,2,3]
Output: 20

Example 6:

Input: nums = [1,2,1,2]
Output: 28

Example 7:

Input: nums = [1,2,3,4]
Output: 50

Constraints:

1 <= nums.length <= 100
1 <= nums[i] <= 100

Hint:

Use a set/heap to keep track of distinct element counts.

Solution:

We solve the problem by enumerating every subarray using two nested loops. For each starting index, we maintain a hash set of seen values and increment the distinct count whenever a new value appears. Then we add the square of the current distinct count to the answer.

Approach

Initialize answer = 0.
Loop over every possible starting index i.
For each i, initialize an empty hash set seen and distinct = 0.
Extend the subarray by moving j from i to n - 1.
If nums[j] is not in seen, add it and increment distinct.
Add distinct * distinct to answer.
Return answer.

Let's implement this solution in PHP: 2913. Subarrays Distinct Element Sum of Squares I

<?php
/**
 * @param Integer[] $nums
 * @return Integer
 */
function sumCounts(array $nums): int
{
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
echo sumCounts([1,2,1]) .  "\n";        // Output: 15
echo sumCounts([1,1]) .  "\n";          // Output: 3
echo sumCounts([1]) .  "\n";            // Output: 1
echo sumCounts([1,1,1]) .  "\n";        // Output: 6
echo sumCounts([1,2,3]) .  "\n";        // Output: 20
echo sumCounts([1,2,1,2]) .  "\n";      // Output: 28
echo sumCounts([1,2,3,4]) .  "\n";      // Output: 50
?>

Explanation:

Every subarray is uniquely represented by (i, j), so the nested loops cover all non-empty subarrays exactly once.
For a fixed i, extending j adds only one new element to the previous subarray nums[i..j-1].
The hash set seen tracks which values already appear in the current subarray.
If the new value is already in seen, the distinct count does not change.
If the new value is new, the distinct count increases by 1.
We square the current distinct count and accumulate it into the final result.

Complexity Analysis

Time Complexity: O(n²) There are O(n²) subarrays. Hash set operations are average O(1).
Space Complexity: O(n) The seen hash set stores at most n distinct values for one starting index.
Constraints: n <= 100, so O(n²) is easily fast enough.

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!

If you want more helpful content like this, feel free to follow me:

LinkedIn
GitHub

3723. Maximize Sum of Squares of Digits

MD ARIFUL HAQUE — Wed, 14 Oct 2026 20:05:02 +0000

3723. Maximize Sum of Squares of Digits

Difficulty: Medium

Topics: Staff, Math, Greedy, Biweekly Contest 168

You are given two positive integers num and sum.

A positive integer n is good if it satisfies both of the following:

The number of digits in n is exactly num.
The sum of digits in n is exactly sum.

The score of a good integer n is the sum of the squares of digits in n.

Return a string denoting the good integer n that achieves the maximum score. If there are multiple possible integers, return the maximum one. If no such integer exists, return an empty string.

Example 1:

Input: num = 2, sum = 3
Output: "30"
Explanation:
- There are 3 good integers: 12, 21, and 30.
  - The score of 12 is 1² + 2² = 5.
  - The score of 21 is 2² + 1² = 5.
  - The score of 30 is 3² + 0² = 9.
- The maximum score is 9, which is achieved by the good integer 30. Therefore, the answer is "30".

Example 2:

Input: num = 2, sum = 17
Output: "98"
Explanation:
- There are 2 good integers: 89 and 98.
  - The score of 89 is 8² + 9² = 145.
  - The score of 98 is 9² + 8² = 145.
- The maximum score is 145. The maximum good integer that achieves this score is 98. Therefore, the answer is "98".

Example 3:

Input: num = 1, sum = 10
Output: ""
Explanation: There are no integers that have exactly 1 digit and whose digits sum to 10. Therefore, the answer is "".

Example 4:

Input: num = 1, sum = 9
Output: "9"
Explanation: The only possible digit is 9.

Example 5:

Input: num = 2, sum = 18
Output: "99"
Explanation: The maximum digit sum for 2 digits is 9 + 9 = 18, so the only valid integer is 99.

Example 6:

Input: num = 3, sum = 18
Output: "990"
Explanation: To maximize the score, use two 9s and one 0: 9² + 9² + 0² = 162. The maximum valid integer is 990.

Example 7:

Input: num = 3, sum = 19
Output: "991"
Explanation: The best digits are two 9s and one 1: 9² + 9² + 1² = 163. The maximum valid integer is 991.

Example 8:

Input: num = 3, sum = 27
Output: "999"
Explanation: The maximum digit sum for 3 digits is 9 + 9 + 9 = 27, so the only valid integer is 999.

Example 9:

Input: num = 3, sum = 28
Output: ""
Explanation: The maximum digit sum for 3 digits is 9 * 3 = 27, so sum 28 is impossible.

Example 10:

Input: num = 4, sum = 1
Output: "1000"
Explanation: The only valid 4-digit integer with digit sum 1 is 1000.

Example 11:

Input: num = 2, sum = 10
Output: "91"
Explanation: The maximum score is 9² + 1² = 82, achieved by both 19 and 91. The maximum valid integer is 91.

Example 12:

Input: num = 5, sum = 45
Output: "99999"
Explanation: The maximum digit sum for 5 digits is 9 * 5 = 45, so the only valid integer is 99999.

Constraints:

1 <= num <= 2 * 10⁵
1 <= sum <= 2 * 10⁶

Hint:

Use a greedy approach.
Fill the leftmost digits with 9s first (as much as possible).

Solution:

We need to handle two types of queries on a power grid where stations can go offline, and I need to find the smallest operational station in the same connected component.

Approach

Let num be the required number of digits and sum be the required digit sum.
If sum > 9 * num, it is impossible to form such a number, so return "".
Compute:
- q = intdiv(sum, 9) — number of 9s we can use.
- r = sum % 9 — leftover digit after placing 9s.
If r == 0, return q copies of '9' followed by num - q copies of '0'.
Otherwise, return q copies of '9', then r, then enough '0's to reach exactly num digits.
This construction is valid because the first digit is never 0 when sum > 0.

Let's implement this solution in PHP: 3723. Maximize Sum of Squares of Digits

<?php
/**
 * @param Integer $num
 * @param Integer $sum
 * @return String
 */
function maxSumOfSquares(int $num, int $sum): string
{
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
echo maxSumOfSquares(2, 3) . "\n";   // Output: "30"
echo maxSumOfSquares(2, 17) . "\n";  // Output: "98"
echo maxSumOfSquares(1, 10) . "\n";  // Output: ""
echo maxSumOfSquares(1, 9) . "\n";   // Output: "9"
echo maxSumOfSquares(2, 18) . "\n";  // Output: "99"
echo maxSumOfSquares(3, 18) . "\n";  // Output: "990"
echo maxSumOfSquares(3, 19) . "\n";  // Output: "991"
echo maxSumOfSquares(3, 27) . "\n";  // Output: "999"
echo maxSumOfSquares(3, 28) . "\n";  // Output: ""
echo maxSumOfSquares(4, 1) . "\n";   // Output: "1000"
echo maxSumOfSquares(2, 10) . "\n";  // Output: "91"
echo maxSumOfSquares(5, 45) . "\n";  // Output: "99999"
?>

Explanation:

To maximize sum of squares, we want digits to be as large and unequal as possible.
The largest allowed digit is 9, so we use as many 9s as possible.
Any remaining sum less than 9 becomes a single digit.
The remaining positions must be 0 because they do not change the digit sum and preserve the required number of digits.
Ordering digits as 9...9 r 0...0 gives the largest possible integer among all numbers with the same maximum score.
Example: num = 2, sum = 17 gives q = 1, r = 8, so the answer is "98".

Complexity Analysis

Time Complexity: O(num) because we build a string of length num.
Space Complexity: O(num) for the returned string.
Auxiliary Space: O(1) excluding the output string.

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!

If you want more helpful content like this, feel free to follow me:

LinkedIn
GitHub

3727. Maximum Alternating Sum of Squares

MD ARIFUL HAQUE — Tue, 13 Oct 2026 15:06:37 +0000

3727. Maximum Alternating Sum of Squares

Difficulty: Medium

Topics: Senior, Array, Greedy, Sorting, Weekly Contest 473

You are given an integer array nums. You may rearrange the elements in any order.

The alternating score of an array arr is defined as:

score = arr[0]² - arr[1]² + arr[2]² - arr[3]² + ...

Return an integer denoting the maximum possible alternating score of nums after rearranging its elements.

Example 1:

Input: nums = [1,2,3]
Output: 12
Explanation:
- A possible rearrangement for nums is [2,1,3], which gives the maximum alternating score among all possible rearrangements.
- The alternating score is calculated as: score = 2² - 1² + 3² = 4 - 1 + 9 = 12

Example 2:

Input: nums = [1,-1,2,-2,3,-3]
Output: 16
Explanation:
- A possible rearrangement for nums is [-3,-1,-2,1,3,2], which gives the maximum alternating score among all possible rearrangements.
- The alternating score is calculated as: score = (-3)² - (-1)² + (-2)² - (1)² + (3)² - (2)² = 9 - 1 + 4 - 1 + 9 - 4 = 16

Example 3:

Input: nums = [5]
Output: 25

Example 4:

Input: nums = [1,2]
Output: 3

Example 5:

Input: nums = [-5,5]
Output: 0

Example 6:

Input: nums = [0,0,0]
Output: 0

Example 7:

Input: nums = [1,2,3,4]
Output: 20

Example 8:

Input: nums = [-4,-3,-2,-1,0]
Output: 28

Example 9:

Input: nums = [100,-100,1]
Output: 19999

Constraints:

1 <= nums.length <= 10⁵
-4 * 10⁴ <= nums[i] <= 4 * 10⁴

Hint:

The score uses squares of values. The original signs of nums don't affect the squared terms.
In the alternating sum, even indices contribute positively and odd indices negatively.

Solution:

We maximize the alternating score by ignoring the original signs of nums, since only squares matter. After squaring all values and sorting them descending, we place the largest ceil(n/2) squares into positive positions and the remaining smaller squares into negative positions.

Approach

Convert every nums[i] into nums[i] * nums[i].
Sort these squared values in descending order.
There are positiveCount = ceil(n / 2) positive slots.
Add the first positiveCount largest squares to the score.
Subtract all remaining smaller squares from the score.
Return the resulting score.

Let's implement this solution in PHP: 3727. Maximum Alternating Sum of Squares

<?php
/**
 * @param Integer[] $nums
 * @return Integer
 */
function maxAlternatingSum(array $nums): int
{
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
echo maxAlternatingSum([1,2,3]) .  "\n";                // Output: 12
echo maxAlternatingSum([1,-1,2,-2,3,-3]) .  "\n";       // Output: 16
echo maxAlternatingSum([5]) .  "\n";                    // Output: 25
echo maxAlternatingSum([1,2]) .  "\n";                  // Output: 3
echo maxAlternatingSum([-5,5]) .  "\n";                 // Output: 0
echo maxAlternatingSum([0,0,0]) .  "\n";                // Output: 0
echo maxAlternatingSum([1,2,3,4]) .  "\n";              // Output: 20
echo maxAlternatingSum([-4,-3,-2,-1,0]) .  "\n";        // Output: 28
echo maxAlternatingSum([100,-100,1]) .  "\n";           // Output: 19999
?>

Explanation:

The alternating score is:
- arr[0]² - arr[1]² + arr[2]² - arr[3]² + ...
Even indices contribute positively, odd indices contribute negatively.
For length n:
- Positive slots = ceil(n / 2)
- Negative slots = floor(n / 2)
To maximize the result, we want the largest possible squares in positive slots and the smallest possible squares in negative slots.
If a larger square were in a negative slot and a smaller square in a positive slot, swapping them would increase the score.
Therefore, sorting descending and assigning the first ceil(n/2) values to positive positions is optimal.

Complexity Analysis

Time Complexity: O(n log n) due to sorting.
Space Complexity: O(n) for the squared-values array.
n <= 10⁵, so this is efficient.

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!

If you want more helpful content like this, feel free to follow me:

LinkedIn
GitHub

2897. Apply Operations on Array to Maximize Sum of Squares

MD ARIFUL HAQUE — Mon, 12 Oct 2026 18:00:07 +0000

2897. Apply Operations on Array to Maximize Sum of Squares

Difficulty: Hard

Topics: Senior Staff, Array, Hash Table, Greedy, Bit Manipulation, Weekly Contest 366

You are given a 0-indexed integer array nums and a positive integer k.

You can do the following operation on the array any number of times:

Choose any two distinct indices i and j and simultaneously update the values of nums[i] to (nums[i] AND nums[j]) and nums[j] to (nums[i] OR nums[j]). Here, OR denotes the bitwise OR operation, and AND denotes the bitwise AND operation.

You have to choose k elements from the final array and calculate the sum of their squares.

Return the maximum sum of squares you can achieve.

Since the answer can be very large, return it modulo 10⁹ + 7.

Example 1:

Input: nums = [2,6,5,8], k = 2
Output: 261
Explanation:
- We can do the following operations on the array:
  - Choose i = 0 and j = 3, then change nums[0] to (2 AND 8) = 0 and nums[3] to (2 OR 8) = 10. The resulting array is nums = [0,6,5,10].
  - Choose i = 2 and j = 3, then change nums[2] to (5 AND 10) = 0 and nums[3] to (5 OR 10) = 15. The resulting array is nums = [0,6,0,15].
- We can choose the elements 15 and 6 from the final array. The sum of squares is 152 + 62 = 261.
- It can be shown that this is the maximum value we can get.

Example 2:

Input: nums = [4,5,4,7], k = 3
Output: 90
Explanation:
- We do not need to apply any operations.
- We can choose the elements 7, 5, and 4 with a sum of squares: 7² + 5² + 4² = 90.
- It can be shown that this is the maximum value we can get.

Example 3:

Input: nums = [1], k = 1
Output: 1

Example 4:

Input: nums = [1,2,4,8], k = 2
Output: 225

Example 5:

Input: nums = [7,7,7], k = 3
Output: 147

Example 6:

Input: nums = [1,1,1], k = 2
Output: 2

Example 7:

Input: nums = [10,10], k = 2
Output: 200

Constraints:

1 <= k <= nums.length <= 10⁵
1 <= nums[i] <= 10⁹

Hint:

The operation described only transfers some bits from one element to another in their binary representation.
To have a maximum sum of squares, it is optimal to greedily make each number as big as possible.

Similar Questions:

3022. Minimize OR of Remaining Elements Using Operations

Solution:

We observe that the allowed operation only redistributes bits between numbers; it never changes how many numbers contain a given bit. Therefore, we count the frequency of every bit, then greedily construct the k largest possible numbers by assigning each bit to as many of those k numbers as possible. Finally, we sum the squares of these k numbers modulo 10⁹ + 7.

Approach

Count how many numbers have each bit set, for bits 0 through 30.
Build k numbers greedily:
- For each of the k positions, create a new value val = 0.
- For every bit b, if cnt[b] > 0, set that bit in val and decrement cnt[b].
- Add val * val to the answer modulo 10⁹ + 7.
Return the accumulated answer.

Let's implement this solution in PHP: 2897. Apply Operations on Array to Maximize Sum of Squares

<?php
/**
 * @param Integer[] $nums
 * @param Integer $k
 * @return Integer
 */
function maxSum(array $nums, int $k): int
{
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
echo maxSum([2,6,5,8], 2) .  "\n";      // Output: 261
echo maxSum([4,5,4,7], 3) .  "\n";      // Output: 90
echo maxSum([1], 1) .  "\n";            // Output: 1
echo maxSum([1,2,4,8], 2) .  "\n";      // Output: 225
echo maxSum([7,7,7], 3) .  "\n";        // Output: 147
echo maxSum([1,1,1], 2) .  "\n";        // Output: 2
echo maxSum([10,10], 2) .  "\n";        // Output: 200
?>

Explanation:

The operation (nums[i] AND nums[j]) and (nums[i] OR nums[j]) preserves the total number of set bits at every bit position.
- If both bits are 0 or both are 1, the counts do not change.
- If one bit is 1 and the other is 0, the 1 simply moves from one number to the other.
To maximize the sum of squares, we want to concentrate bits into the largest possible numbers because squares grow faster for larger values.
For each bit with frequency c, at most min(c, k) of the chosen k numbers can contain that bit.
The greedy construction assigns each available bit to the first min(c, k) numbers, making the earlier numbers as large as possible.
This produces the optimal k numbers.

Complexity Analysis

Time Complexity: O(31 * (n + k)), which is effectively O(n + k) since 31 is constant.
Space Complexity: O(31), which is O(1).

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!

If you want more helpful content like this, feel free to follow me:

LinkedIn
GitHub

2728. Sum of Squares of Special Elements

MD ARIFUL HAQUE — Sun, 11 Oct 2026 17:43:39 +0000

2728. Sum of Squares of Special Elements

Difficulty: Easy

Topics: Mid Level, Array, Enumeration, Weekly Contest 354

You are given a 1-indexed integer array nums of length n.

An element nums[i] of nums is called special if i divides n, i.e. n % i == 0.

Return the sum of the squares of all special elements of nums.

Example 1:

Input: nums = [1,2,3,4]
Output: 21
Explanation:
- There are exactly 3 special elements in nums: nums[1] since 1 divides 4, nums[2] since 2 divides 4, and nums[4] since 4 divides 4.
- Hence, the sum of the squares of all special elements of nums is nums[1] * nums[1] + nums[2] * nums[2] + nums[4] * nums[4] = 1 * 1 + 2 * 2 + 4 * 4 = 21.

Example 2:

Input: nums = [2,7,1,19,18,3]
Output: 63
Explanation:
- There are exactly 4 special elements in nums: nums[1] since 1 divides 6, nums[2] since 2 divides 6, nums[3] since 3 divides 6, and nums[6] since 6 divides 6.
- Hence, the sum of the squares of all special elements of nums is nums[1] * nums[1] + nums[2] * nums[2] + nums[3] * nums[3] + nums[6] * nums[6] = 2 * 2 + 7 * 7 + 1 * 1 + 3 * 3 = 63.

Example 3:

Input: nums = [5]
Output: 25

Example 4:

Input: nums = [1,2]
Output: 5

Example 5:

Input: nums = [50,50]
Output: 5000

Constraints:

1 <= nums.length == n <= 50
1 <= nums[i] <= 50

Hint:

Iterate over all the elements of the array. For each index i, check if it is special using the modulo operator.
if n%i == 0, index i is special, and you should add nums[i] to the answer.

Similar Questions:

Solution:

We solve the problem by iterating over the 1-indexed positions of nums, checking whether each position i divides the array length n. If it does, we add the square of the corresponding element to the total sum.

Approach

Let n = count($nums).
Iterate i from 1 to n, because the problem uses 1-based indexing.
Check if n % i == 0.
If true, i is a special index.
Convert the 1-based index to PHP’s 0-based index using $i - 1.
Add nums[$i - 1] * nums[$i - 1] to the result.
Return the accumulated sum.

Let's implement this solution in PHP: 2728. Sum of Squares of Special Elements

<?php
/**
 * @param Integer[] $nums
 * @return Integer
 */
function sumOfSquares(array $nums): int
{
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
echo sumOfSquares([1,2,3,4]) .  "\n";               // Output: 21
echo sumOfSquares([2,7,1,19,18,3]) .  "\n";         // Output: 63
echo sumOfSquares([5]) .  "\n";                     // Output: 25
echo sumOfSquares([1,2]) .  "\n";                   // Output: 5
echo sumOfSquares([50,50]) .  "\n";                 // Output: 5000
?>

Explanation:

In PHP, arrays start at index 0, but the problem defines special positions using 1-based indexing.
For example, nums[1] in the problem corresponds to $nums[0] in PHP.
The condition n % i == 0 checks whether position i divides the total length n.
For each valid special position, we square the value and add it to the answer.
This directly follows the hint: check divisibility and accumulate squared values.

Complexity Analysis

Time Complexity: O(n) — we check each index from 1 to n exactly once.
Space Complexity: O(1) — only a few scalar variables are used.

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!

If you want more helpful content like this, feel free to follow me:

LinkedIn
GitHub

2333. Minimum Sum of Squared Difference

MD ARIFUL HAQUE — Sat, 10 Oct 2026 15:03:58 +0000

2333. Minimum Sum of Squared Difference

Difficulty: Medium

Topics: Staff, Array, Binary Search, Greedy, Sorting, Heap (Priority Queue), Biweekly Contest 82

You are given two positive 0-indexed integer arrays nums1 and nums2, both of length n.

The sum of squared difference of arrays nums1 and nums2 is defined as the sum of (nums1[i] - nums2[i])² for each 0 <= i < n.

You are also given two positive integers k1 and k2. You can modify any of the elements of nums1 by +1 or -1 at most k1 times. Similarly, you can modify any of the elements of nums2 by +1 or -1 at most k2 times.

Return the minimum sum of squared difference after modifying array nums1 at most k1 times and modifying array nums2 at most k2 times.

Note: You are allowed to modify the array elements to become negative integers.

Example 1:

Input: nums1 = [1,2,3,4], nums2 = [2,10,20,19], k1 = 0, k2 = 0
Output: 579
Explanation:
- The elements in nums1 and nums2 cannot be modified because k1 = 0 and k2 = 0.
- The sum of square difference will be: (1 - 2)² + (2 - 10)² + (3 - 20)² + (4 - 19)² = 579.

Example 2:

Input: nums1 = [1,4,10,12], nums2 = [5,8,6,9], k1 = 1, k2 = 1
Output: 43
Explanation:
- One way to obtain the minimum sum of square difference is:
- Increase nums1[0] once.
- Increase nums2[2] once.
- The minimum of the sum of square difference will be: (2 - 5)² + (4 - 8)² + (10 - 7)² + (12 - 9)² = 43.
- Note that, there are other ways to obtain the minimum of the sum of square difference, but there is no way to obtain a sum smaller than 43.

Example 3:

Input: nums1 = [1,1], nums2 = [1,1], k1 = 100, k2 = 100
Output: 0

Example 4:

Input: nums1 = [1,2,3], nums2 = [4,5,6], k1 = 5, k2 = 4
Output: 0

Example 5:

Input: nums1 = [0], nums2 = [10], k1 = 3, k2 = 4
Output: 9

Example 6:

Input: nums1 = [0], nums2 = [10], k1 = 4, k2 = 4
Output: 4

Example 7:

Input: nums1 = [100000], nums2 = [0], k1 = 1000000000, k2 = 1000000000
Output: 0

Constraints:

n == nums1.length == nums2.length
1 <= n <= 10⁵
0 <= nums1[i], nums2[i] <= 10⁵
0 <= k1, k2 <= 10⁹

Hint:

There is no difference between the purpose of k1 and k2. Adding +1 to one element in nums1 is same as performing -1 to one element in nums2, and vice versa.
Reduce the sum of squared difference greedily. One operation of k should use the index that has the current maximum difference.
Binary search the maximum difference for the final result.

Similar Questions:

Solution:

We combine k1 and k2 into one total budget K = k1 + k2, because increasing nums1[i] by 1 and decreasing nums2[i] by 1 both reduce abs(nums1[i] - nums2[i]) by 1. We then binary search the smallest possible maximum remaining difference m after using at most K operations. Finally, we reduce all differences greater than m down to m, use any leftover operations to reduce some m values to m - 1, and compute the minimum sum of squares.

Approach

Compute d[i] = abs(nums1[i] - nums2[i]) for every index.
Let K = k1 + k2. The two modification budgets are interchangeable for reducing absolute differences.
Binary search the target maximum difference m in [0, max(d)].
For a candidate m, the minimum operations needed to make every difference <= m is:
- sum(d[i] - m) for all d[i] > m.
If this cost is <= K, then m is feasible; otherwise, it is too small.
After binary search, m is the smallest feasible maximum remaining difference.
Compute the exact cost to reduce every d[i] > m down to m.
Let remain = K - cost.
Build the answer:
- If d[i] > m, contribute m².
- Otherwise, contribute d[i]².
Each leftover operation can reduce one current difference from m to m - 1.
- Decrease in square: m² - (m - 1)² = 2m - 1.
Subtract remain * (2m - 1) from the answer.
If m == 0, all differences can become zero, so return 0.

Let's implement this solution in PHP: 2333. Minimum Sum of Squared Difference

<?php
/**
 * @param Integer[] $nums1
 * @param Integer[] $nums2
 * @param Integer $k1
 * @param Integer $k2
 * @return Integer
 */
function minSumSquareDiff(array $nums1, array $nums2, int $k1, int $k2): int
{
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
echo minSumSquareDiff([1,2,3,4],[2,10,20,19],0,0) .  "\n";                  // Output: 579
echo minSumSquareDiff([1,4,10,12],[5,8,6,9],1,1) .  "\n";                   // Output: 43
echo minSumSquareDiff([1,1],[1,1],100,100) .  "\n";                         // Output: 0
echo minSumSquareDiff([1,2,3],[4,5,6],5,4) .  "\n";                         // Output: 0
echo minSumSquareDiff([0],[10],3,4) .  "\n";                                // Output: 9
echo minSumSquareDiff([0],[10],4,4) .  "\n";                                // Output: 4
echo minSumSquareDiff([100000],[0],1000000000,1000000000) .  "\n";          // Output: 0
?>

Explanation:

k1 and k2 are equivalent because changing either array by ±1 changes the absolute difference by 1.
For a fixed maximum allowed difference m, the cheapest way is to reduce only differences larger than m.
The feasibility condition is monotonic:
- Larger m requires fewer or equal operations.
- Smaller m requires more operations.
Therefore, binary search can find the smallest feasible m.
After making all differences <= m, some operations may remain.
Since m is the smallest feasible maximum, the leftover operations cannot reduce all remaining m values to m - 1.
Instead, they reduce as many m values as possible by 1, which is captured by remain * (2m - 1).

Complexity Analysis

Time Complexity: O(n log M), where M = max(abs(nums1[i] - nums2[i])). Since M <= 10⁵, this is effectively O(n log 10⁵).
Space Complexity: O(n) for storing the absolute differences.

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!

If you want more helpful content like this, feel free to follow me:

LinkedIn
GitHub

1541. Minimum Insertions to Balance a Parentheses String

MD ARIFUL HAQUE — Fri, 09 Oct 2026 17:57:31 +0000

1541. Minimum Insertions to Balance a Parentheses String

Difficulty: Medium

Topics: Staff, String, Stack, Greedy, Bracket Sequences, Biweekly Contest 32

Given a parentheses string s containing only the characters '(' and ')'. A parentheses string is balanced if:

Any left parenthesis '(' must have a corresponding two consecutive right parenthesis '))'.
Left parenthesis '(' must go before the corresponding two consecutive right parenthesis '))'.

In other words, we treat '(' as an opening parenthesis and '))' as a closing parenthesis.

For example, "())", "())(())))" and "(())())))" are balanced, ")()", "()))" and "(()))" are not balanced.

You can insert the characters '(' and ')' at any position of the string to balance it if needed.

Return the minimum number of insertions needed to make s balanced.

Example 1:

Input: s = "(()))"
Output: 1
Explanation: The second '(' has two matching '))', but the first '(' has only ')' matching. We need to add one more ')' at the end of the string to be "(())))" which is balanced.

Example 2:

Input: s = "())"
Output: 0
Explanation: The string is already balanced.

Example 3:

Input: s = "))())("
Output: 3
Explanation: Add '(' to match the first '))', Add '))' to match the last '('.

Example 4:

Input: s = ")"
Output: 2

Example 5:

Input: s = "()"
Output: 1

Example 6:

Input: s = "((("
Output: 6

Example 7:

Input: s = "(()"
Output: 3

Example 8:

Input: s = "())())"
Output: 0

Example 9:

Input: s = "()())"
Output: 1

Example 10:

Input: s = "))"
Output: 1

Example 11:

Input: s = ")("
Output: 4

Example 12:

Input: s = "))("
Output: 3

Constraints:

1 <= s.length <= 10⁵
s consists of '(' and ')' only.

Hint:

Use a stack to keep opening brackets. If you face single closing ')' add 1 to the answer and consider it as '))'.
If you have '))' with empty stack, add 1 to the answer, If after finishing you have x opening remaining in the stack, add 2x to the answer.

Similar Questions:

1963. Minimum Number of Swaps to Make the String Balanced

Solution:

We scan s left-to-right, tracking unmatched '(' and greedily inserting only the characters needed to form valid '))' closures. This gives the minimum insertions in O(n) time and O(1) extra space.

Approach

Initialize $open = 0 for unmatched '(' and $ans = 0 for insertions.
Traverse the string once.
When seeing '(', increment $open.
When seeing ')':
- If the next character is also ')' and $open > 0, consume both as '))', decrement $open, and skip the next character.
- Else if $open > 0, the current ')' is a lone closing parenthesis; insert one more ')', increment $ans, and decrement $open.
- Else there is no unmatched '(':
  - If the next character is ')', insert '(' before '))', increment $ans, and skip the next character.
  - Otherwise, insert both '(' and ')', adding 2 to $ans.
After the loop, each remaining unmatched '(' needs '))', so add 2 * $open to $ans.

Let's implement this solution in PHP: 1541. Minimum Insertions to Balance a Parentheses String

<?php
/**
 * @param String $s
 * @return Integer
 */
function minInsertions(string $s): int
{
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
echo minInsertions("(()))") .  "\n";        // Output: 1
echo minInsertions("())") .  "\n";          // Output: 0
echo minInsertions("))())(") .  "\n";       // Output: 3
echo minInsertions(")") .  "\n";            // Output: 2
echo minInsertions("()") .  "\n";           // Output: 1
echo minInsertions("(((") .  "\n";          // Output: 6
echo minInsertions("(()") .  "\n";          // Output: 3
echo minInsertions("())())") .  "\n";       // Output: 0
echo minInsertions("()())") .  "\n";        // Output: 1
echo minInsertions("))") .  "\n";           // Output: 1
echo minInsertions(")(") .  "\n";           // Output: 4
echo minInsertions("))(") .  "\n";          // Output: 3
?>

Explanation:

A valid closing unit is exactly '))', not a single ')'.
Greedy matching is safe because each '))' can only close an earlier unmatched '('.
If an unmatched '(' exists and only one ')' is available, we must insert the missing second ')'.
If no unmatched '(' exists, a '))' needs an inserted '('; a lone ')' needs both an inserted '(' and an extra ')'.
Any leftover '(' at the end has no closure, so each costs two insertions.

Complexity Analysis

Time: O(n) — one pass over the string; skipped characters are not revisited.
Space: O(1) — only integer counters are used.

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!

If you want more helpful content like this, feel free to follow me:

LinkedIn
GitHub

1021. Remove Outermost Parentheses

MD ARIFUL HAQUE — Thu, 08 Oct 2026 17:20:12 +0000

1021. Remove Outermost Parentheses

Difficulty: Easy

Topics: Staff, String, Stack, Bracket Sequences, Weekly Contest 131

A valid parentheses string is either empty "", "(" + A + ")", or A + B, where A and B are valid parentheses strings, and + represents string concatenation.

For example, "", "()", "(())()", and "(()(()))" are all valid parentheses strings.

A valid parentheses string s is primitive if it is nonempty, and there does not exist a way to split it into s = A + B, with A and B nonempty valid parentheses strings.

Given a valid parentheses string s, consider its primitive decomposition: s = P₁ + P₂ + ... + Pₖ, where Pᵢ are primitive valid parentheses strings.

Return s after removing the outermost parentheses of every primitive string in the primitive decomposition of s.

Example 1:

Input: s = "(()())(())"
Output: "()()()"
Explanation:
- The input string is "(()())(())", with primitive decomposition "(()())" + "(())".
- After removing outer parentheses of each part, this is "()()" + "()" = "()()()".

Example 2:

Input: s = "(()())(())(()(()))"
Output: "()()()()(())"
Explanation:
- The input string is "(()())(())(()(()))", with primitive decomposition "(()())" + "(())" + "(()(()))".
- After removing outer parentheses of each part, this is "()()" + "()" + "(())" = "()()()()(())".

Example 3:

Input: s = "()()"
Output: ""
Explanation:
- The input string is "()()", with primitive decomposition "()" + "()".
- After removing outer parentheses of each part, this is "" + "" = "".

Example 4:

Input: s = "()"
Output: ""

Example 5:

Input: s = "(())"
Output: "()"

Example 6:

Input: s = "((()))"
Output: "(())"

Example 7:

Input: s = "(()(()))"
Output: "()(())"

Example 8:

Input: s = "()(())()"
Output: "()"

Example 9:

Input: s = "((()))()"
Output: "(())"

Example 10:

Input: s = "((()()))"
Output: "(()())"

Constraints:

1 <= s.length <= 10⁵
s[i] is either '(' or ')'.
s is a valid parentheses string.

Hint:

Can you find the primitive decomposition? The number of ( and ) characters must be equal.

Solution:

We scan the valid parentheses string once while tracking the current nesting depth. For each primitive valid parentheses component, we skip its first '(' and its matching last ')', while keeping every inner parenthesis. This directly builds the required result without explicitly splitting the string into primitive components.

Approach

Initialize result = "" and depth = 0.
Traverse each character of s.
If the character is '(':
- Append it only when depth > 0.
- Then increment depth.
If the character is ')':
- Decrement depth first.
- Append it only when depth > 0 after decrementing.
Return result.

Let's implement this solution in PHP: 1021. Remove Outermost Parentheses

<?php
/**
 * @param String $s
 * @return String
 */
function removeOuterParentheses(string $s): string
{
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
echo removeOuterParentheses("(()())(())") .  "\n";              // Output: "()()()"
echo removeOuterParentheses("(()())(())(()(()))") .  "\n";      // Output: "()()()()(())"
echo removeOuterParentheses("()()") .  "\n";                    // Output: ""
echo removeOuterParentheses("()") .  "\n";                      // Output: ""
echo removeOuterParentheses("(())") .  "\n";                    // Output: "()"
echo removeOuterParentheses("((()))") .  "\n";                  // Output: "(())"
echo removeOuterParentheses("(()(()))") .  "\n";                // Output: "()(())"
echo removeOuterParentheses("()(())()") .  "\n";                // Output: "()"
echo removeOuterParentheses("((()))()") .  "\n";                // Output: "(())"
echo removeOuterParentheses("((()()))") .  "\n";                // Output: "(()())"
?>

Explanation:

A primitive valid parentheses string starts when depth goes from 0 to 1.
The opening '(' that starts a primitive part is outermost, so we skip it by checking depth > 0 before appending.
Inner '(' characters occur when depth is already greater than 0, so they are kept.
For ')', we decrement first because this closing bracket may end the current primitive part.
If depth becomes 0, that ')' is the outermost closing bracket, so we skip it.
If depth remains greater than 0, it is an inner closing bracket, so we keep it.
This works naturally for concatenated primitive strings such as "(()())(())".

Complexity Analysis

Time Complexity: O(n), where n is the length of s. We traverse the string once.
Space Complexity: O(n) for the output string. Auxiliary space is O(1) because only a few variables are used.

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!

If you want more helpful content like this, feel free to follow me:

LinkedIn
GitHub

TouchGrass AI: Local AI that gets you outside

MD ARIFUL HAQUE — Wed, 07 Oct 2026 21:44:44 +0000

This is a submission for the Hacktoberfest Open-Source AI Challenge Week 1: Touch Grass

What I Built

TouchGrass AI is a local-first outdoor companion for people who want help getting started—and a reason to put their phone away once they do.

It turns a few details, such as activity, location, and available time, into a practical outdoor mission. It also includes garden and beginner birding plans, plus a field journal for saving observations locally.

The idea is simple: AI should help you get to the park, garden, or trail—not keep you chatting with a screen. Plans include a safety check and a reminder to put the phone away. The app does not provide live weather or trail conditions, so users are prompted to verify current local conditions themselves.

Demo

Video demo: 60-second TouchGrass AI walkthrough
Animated SVG: Animated demo
Live app: No public deployment yet. The app currently runs locally at http://localhost:8081/; that address is not accessible to other readers.

The recording shows the actual site, a 45-minute birding mission, and saving a field observation. It also includes clearly labeled concept scenes for bird-photo capture and analysis; those features are not implemented. The offline scene simulates disconnecting the recording browser tab, not a full offline field test.

Code

GitHub repository

The project is MIT-licensed and runs with Docker Compose. Missions and field notes are stored in a local SQLite database.

How I Built It

The app uses PHP 8.5, a browser-based PWA shell, SQLite, Docker Compose, and Ollama-compatible local inference. The default model is Gemma 3 (gemma3:4b). The PHP app sends prompts to Ollama over the local Docker network rather than calling a hosted AI API.

Browser / PWA
    |
    v
PHP 8.5 app ---- SQLite
    |
    v
Local Ollama runtime ---- Gemma 3

The model can be changed through configuration without rewriting the app's AI integration. Once the model is downloaded, the app and inference service can run without internet access, provided they are available on the user's device or local network.

Why Does Open Innovation Matter?

Outdoor plans and field notes can reveal personal routines and locations. Running inference locally gives users the option to keep that data on infrastructure they control instead of sending every request to a hosted AI provider.

Open-weight models and an Ollama-compatible interface also make experimentation accessible: developers can inspect and adapt the prompts, try different models, and improve the project without depending on a single AI vendor or API key. That flexibility matters for a tool intended to work beyond reliable connectivity.

My Agent Session

Optional: add a saved DevRelay session link or embed it here:

{% agent_session YOUR_SESSION_ID_OR_SLUG %}

Prize Categories

Overall challenge entry. No partner category claimed.