DEV Community: MD ARIFUL HAQUE

2574. Left and Right Sum Differences

MD ARIFUL HAQUE — Sat, 06 Jun 2026 17:55:55 +0000

2574. Left and Right Sum Differences

Difficulty: Easy

Topics: Mid Level, Array, Prefix Sum, Weekly Contest 334

You are given a 0-indexed integer array nums of size n.

Define two arrays leftSum and rightSum where:

leftSum[i] is the sum of elements to the left of the index i in the array nums. If there is no such element, leftSum[i] = 0.
rightSum[i] is the sum of elements to the right of the index i in the array nums. If there is no such element, rightSum[i] = 0.

Return an integer array answer of size n where answer[i] = |leftSum[i] - rightSum[i]|.

Example 1:

Input: nums = [10,4,8,3]
Output: [15,1,11,22]
Explanation:
- The array leftSum is [0,10,14,22] and the array rightSum is [15,11,3,0].
- The array answer is [|0 - 15|,|10 - 11|,|14 - 3|,|22 - 0|] = [15,1,11,22].

Example 2:

Input: nums = [1]
Output: [0]
Explanation:
- The array leftSum is [0] and the array rightSum is [0].
- The array answer is [|0 - 0|] = [0].

Constraints:

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

Hint:

For each index i, maintain two variables leftSum and rightSum.
Iterate on the range j: [0 … i - 1] and add nums[j] to the leftSum and similarly iterate on the range j: [i + 1 … nums.length - 1] and add nums[j] to the rightSum.

Similar Questions:

Solution:

The solution computes the absolute difference between the sum of elements to the left and the sum of elements to the right for each index in the array. It uses prefix and suffix sums to achieve this efficiently without nested loops.

Approach:

Use prefix sums to calculate leftSum[i] as the sum of all elements before index i.
Use suffix sums to calculate rightSum[i] as the sum of all elements after index i.
For each index i, compute the absolute difference between leftSum[i] and rightSum[i].

Let's implement this solution in PHP: 2574. Left and Right Sum Differences

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

// Test cases
echo leftRightDifference([10,4,8,3]) . "\n";        // Output: [15,1,11,22]
echo leftRightDifference([1]) . "\n";               // Output: [0]
?>

Explanation:

Create arrays leftSum and rightSum of the same length as nums, initialized to 0.
First pass from left to right:
- leftSum[i] = leftSum[i-1] + nums[i-1]
- This accumulates sums of elements before the current index.
Second pass from right to left:
- rightSum[i] = rightSum[i+1] + nums[i+1]
- This accumulates sums of elements after the current index.
Third pass through indices:
- Compute answer[i] = |leftSum[i] - rightSum[i]|
Return the answer array.

Complexity

Time Complexity: O(n) — each element is processed three times (once for left sum, once for right sum, once for answer).
Space Complexity: O(n) — two extra arrays of size n are used for left and right sums.

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

3753. Total Waviness of Numbers in Range II

MD ARIFUL HAQUE — Fri, 05 Jun 2026 15:48:08 +0000

3753. Total Waviness of Numbers in Range II

Difficulty: Hard

Topics: Senior Staff, Math, Dynamic Programming, Biweekly Contest 170

You are given two integers num1 and num2 representing an inclusive range [num1, num2].

The waviness of a number is defined as the total count of its peaks and valleys:

A digit is a peak if it is strictly greater than both of its immediate neighbors.
A digit is a valley if it is strictly less than both of its immediate neighbors.
The first and last digits of a number cannot be peaks or valleys.
Any number with fewer than 3 digits has a waviness of 0.

Return the total sum of waviness for all numbers in the range [num1, num2].

Example 1:

Input: num1 = 120, num2 = 130
Output: 3
Explanation:
- In the range [120, 130]:
- 120: middle digit 2 is a peak, waviness = 1.
- 121: middle digit 2 is a peak, waviness = 1.
- 130: middle digit 3 is a peak, waviness = 1.
- All other numbers in the range have a waviness of 0.
- Thus, total waviness is 1 + 1 + 1 = 3.

Example 2:

Input: num1 = 198, num2 = 202
Output: 3
Explanation:
- In the range [198, 202]:
  - 198: middle digit 9 is a peak, waviness = 1.
  - 201: middle digit 0 is a valley, waviness = 1.
  - 202: middle digit 0 is a valley, waviness = 1.
  - All other numbers in the range have a waviness of 0.
- Thus, total waviness is 1 + 1 + 1 = 3.

Example 3:

Input: num1 = 4848, num2 = 4848
Output: 2
Explanation: Number 4848: the second digit 8 is a peak, and the third digit 4 is a valley, giving a waviness of 2.

Example 4:

Input: num1 = 63, num2 = 101
Output: 1

Constraints:

1 <= num1 <= num2 <= 10¹⁵

Hint:

Use digit dynamic programming
Build a digit-DP state (position, tight, lastDigit, secondLastDigit)

Solution:

This solution calculates the total sum of waviness for all numbers in a given inclusive range [num1, num2].

Waviness is defined as the count of peaks and valleys in the digit sequence of a number (excluding first and last digits).

The approach uses digit dynamic programming (digit DP) to efficiently process ranges up to 10^15, avoiding brute-force enumeration.

The function totalWaviness(num1, num2) computes the result as solve(num2) - solve(num1 - 1), where solve(n) returns the total waviness for [1, n].

Approach:

Digit DP – We recursively process digits from most significant to least significant.
State – (position, tight, started, secondLast, last) tracks:
- current index in the number
- whether we are bound by the prefix of n (tight)
- whether we have started placing non-leading digits (started)
- the previous two digits (secondLast, last) to detect peaks/valleys
Memoization – For !tight states, we store results to reuse across different numbers.
Contribution counting – When we place a new digit:
- If we have at least 3 digits so far (secondLast !== -1), we check if the middle digit (last) is a peak or valley.
- If yes, we add 1 × (number of valid suffixes) to the waviness sum.
Base case – When all digits are placed (pos == len), return count = 1, waviness = 0.
Range subtraction – totalWaviness(num1, num2) = solve(num2) - solve(num1 - 1).

Let's implement this solution in PHP: 3753. Total Waviness of Numbers in Range II

<?php
/**
 * @param Integer $num1
 * @param Integer $num2
 * @return Integer
 */
function totalWaviness(int $num1, int $num2): int
{
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

/**
 * @param int $n
 * @return int|mixed
 */
function sumWavinessUpTo(int $n): mixed
{
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
echo totalWaviness(120, 130) . "\n";            // Output: 3
echo totalWaviness(198, 202) . "\n";            // Output: 3
echo totalWaviness(4848, 4848) . "\n";          // Output: 2
echo totalWaviness(63, 101) . "\n";             // Output: 1
?>

Explanation:

Peak & Valley definition
- A digit d is a peak if prev < d > next.
- A digit d is a valley if prev > d < next.
- First and last digits are ignored.
Digit DP state We need the last two digits to know if the current position (as the second last) is a peak/valley when the next digit is chosen.
Transition
- At position pos, we try digits 0..limit:
  - If not started and digit is 0, stay in not started.
  - If not started and digit > 0, start the number, store it as last, secondLast = -1.
  - If started, compute if last (which is the middle digit between secondLast and digit) is peak/valley, and add to waviness accordingly.
Memoization The result for a state (pos, started, secondLast, last) with tight = 0 can be reused across different higher prefixes.
Complexity State count is O(len × 2 × 10 × 10) with len ≤ 16 → very fast.

Complexity

Time Complexity: O(len × 2 × 10 × 10 × 10) ≈ O(16 × 1000) = O(16000) per solve(n), which is trivial for input sizes up to 10¹⁵.
Space Complexity: O(len × 2 × 10 × 10) for memoization table.

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

3751. Total Waviness of Numbers in Range I

MD ARIFUL HAQUE — Thu, 04 Jun 2026 17:55:07 +0000

3751. Total Waviness of Numbers in Range I

Difficulty: Medium

Topics: Senior, Math, Dynamic Programming, Enumeration, Biweekly Contest 170

You are given two integers num1 and num2 representing an inclusive range [num1, num2].

The waviness of a number is defined as the total count of its peaks and valleys:

A digit is a peak if it is strictly greater than both of its immediate neighbors.
A digit is a valley if it is strictly less than both of its immediate neighbors.
The first and last digits of a number cannot be peaks or valleys.
Any number with fewer than 3 digits has a waviness of 0.

Return the total sum of waviness for all numbers in the range [num1, num2].

Example 1:

Input: num1 = 120, num2 = 130
Output: 3
Explanation:
- In the range [120, 130]:
- 120: middle digit 2 is a peak, waviness = 1.
- 121: middle digit 2 is a peak, waviness = 1.
- 130: middle digit 3 is a peak, waviness = 1.
- All other numbers in the range have a waviness of 0.
- Thus, total waviness is 1 + 1 + 1 = 3.

Example 2:

Input: num1 = 198, num2 = 202
Output: 3
Explanation:
- In the range [198, 202]:
- 198: middle digit 9 is a peak, waviness = 1.
- 201: middle digit 0 is a valley, waviness = 1.
- 202: middle digit 0 is a valley, waviness = 1.
- All other numbers in the range have a waviness of 0.Thus,
- total waviness is 1 + 1 + 1 = 3.

Example 3:

Input: num1 = 4848, num2 = 4848
Output: 2
Explanation: Number 4848: the second digit 8 is a peak, and the third digit 4 is a valley, giving a waviness of 2.

Constraints:

1 <= num1 <= num2 <= 10⁵

Hint:

Use bruteforce

Solution:

We compute the waviness of each number in the inclusive range from num1 to num2 and sum the results. Waviness counts internal digits that are strictly greater than both neighbors (peaks) or strictly less than both neighbors (valleys). Numbers with fewer than 3 digits automatically have 0 waviness.

Approach:

Iterate through every number in the range.
Convert each number to a string to access its digits.
Skip numbers with fewer than 3 digits.
Check each interior digit (excluding first and last) for peak or valley conditions.
Sum the waviness for the number.
Accumulate the total over all numbers.

Let's implement this solution in PHP: 3751. Total Waviness of Numbers in Range I

<?php
/**
 * @param Integer $num1
 * @param Integer $num2
 * @return Integer
 */
function totalWaviness(int $num1, int $num2): int
{
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

/**
 * @param $num
 * @return int
 */
function wavinessOfNumber($num): int
{
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
echo totalWaviness(120, 130) . "\n";            // Output: 3
echo totalWaviness(198, 202) . "\n";            // Output: 3
echo totalWaviness(4848, 4848) . "\n";          // Output: 2
?>

Explanation:

Brute force enumeration is feasible here because the range is at most 100,000 numbers.
wavinessOfNumber() handles the logic for a single number:
- Split digits into an array.
- Loop from index 1 to len-2 (inclusive) to avoid first and last digits.
- Compare each digit with its immediate left and right neighbors.
- Increment waviness if the digit is a peak (mid > left && mid > right) or a valley (mid < left && mid < right).
The main function totalWaviness() loops from num1 to num2, calling the helper and adding to the total.

Complexity

Time Complexity: O(N * D) where N = range size (num2 - num1 + 1) and D = max digit length (≤ 6 for numbers ≤ 10⁵).
- Here, D is small, so effectively O(N).
Space Complexity: O(D), as 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

3635. Earliest Finish Time for Land and Water Rides II

MD ARIFUL HAQUE — Wed, 03 Jun 2026 15:29:17 +0000

3635. Earliest Finish Time for Land and Water Rides II

Difficulty: Medium

Topics: Staff, Array, Two Pointers, Binary Search, Greedy, Sorting, Biweekly Contest 162

You are given two categories of theme park attractions: land rides and water rides.

Land rides
- landStartTime[i] – the earliest time the iᵗʰ land ride can be boarded.
- landDuration[i] – how long the iᵗʰ land ride lasts.
Water rides
- waterStartTime[j] – the earliest time the jᵗʰ water ride can be boarded.
- waterDuration[j] – how long the jᵗʰ water ride lasts.

A tourist must experience exactly one ride from each category, in either order.

A ride may be started at its opening time or any later moment.
If a ride is started at time t, it finishes at time t + duration.
Immediately after finishing one ride the tourist may board the other (if it is already open) or wait until it opens.

Return the earliest possible time at which the tourist can finish both rides.

Example 1:

Input: landStartTime = [2,8], landDuration = [4,1], waterStartTime = [6], waterDuration = [3]
Output: 9
Explanation:
- Plan A (land ride 0 → water ride 0):
  - Start land ride 0 at time landStartTime[0] = 2. Finish at 2 + landDuration[0] = 6.
  - Water ride 0 opens at time waterStartTime[0] = 6. Start immediately at 6, finish at 6 + waterDuration[0] = 9.
- Plan B (water ride 0 → land ride 1):
  - Start water ride 0 at time waterStartTime[0] = 6. Finish at 6 + waterDuration[0] = 9.
  - Land ride 1 opens at landStartTime[1] = 8. Start at time 9, finish at 9 + landDuration[1] = 10.
- Plan C (land ride 1 → water ride 0):
  - Start land ride 1 at time landStartTime[1] = 8. Finish at 8 + landDuration[1] = 9.
  - Water ride 0 opened at waterStartTime[0] = 6. Start at time 9, finish at 9 + waterDuration[0] = 12.
- Plan D (water ride 0 → land ride 0):
  - Start water ride 0 at time waterStartTime[0] = 6. Finish at 6 + waterDuration[0] = 9.
  - Land ride 0 opened at landStartTime[0] = 2. Start at time 9, finish at 9 + landDuration[0] = 13.
- Plan A gives the earliest finish time of 9.

Example 2:

Input: landStartTime = [5], landDuration = [3], waterStartTime = [1], waterDuration = [10]
Output: 14
Explanation:
- Plan A (water ride 0 → land ride 0):
  - Start water ride 0 at time waterStartTime[0] = 1. Finish at 1 + waterDuration[0] = 11.
  - Land ride 0 opened at landStartTime[0] = 5. Start immediately at 11 and finish at 11 + landDuration[0] = 14.
- Plan B (land ride 0 → water ride 0):
  - Start land ride 0 at time landStartTime[0] = 5. Finish at 5 + landDuration[0] = 8.
  - Water ride 0 opened at waterStartTime[0] = 1. Start immediately at 8 and finish at 8 + waterDuration[0] = 18.
- Plan A provides the earliest finish time of 14.

Constraints:

1 <= n, m <= 5 * 10⁴
landStartTime.length == landDuration.length == n
waterStartTime.length == waterDuration.length == m
1 <= landStartTime[i], landDuration[i], waterStartTime[j], waterDuration[j] <= 10⁵

Hint:

Sort each ride list by opening time and build a prefix minimum of ride durations and a suffix minimum of ride finish times (start + duration).
Try both orders, land then water and water then land. For each ride in the first list compute finish1 = start1 + duration1.
Binary‑search the second list (sorted by start) to split rides into those with start <= finish1 and those with start > finish1. Use the prefix minimum duration on the early group to get an earliest finish of finish1 + minDuration and the suffix minimum finish time on the late group.
For each pairing take the smaller finish time and track the overall minimum.

Solution:

The problem requires finding the earliest finish time for a tourist who must take exactly one land ride and one water ride, in either order.

The solution sorts both lists by start time, then uses prefix minimum durations and suffix minimum finish times combined with binary search to efficiently compute the best finish time for each possible first ride.

Approach:

Two Orders
- Consider both possible sequences: land ride first then water ride, and water ride first then land ride.
Sorting Sort both ride lists by start time to enable binary search and efficient preprocessing.
Preprocessing For the second category (the one taken after the first ride), compute:
- Prefix minimum of durations (for rides that can start before the first ride ends)
- Suffix minimum of finish times (for rides that start after the first ride ends)
Binary Search After finishing the first ride at time finish1, binary search in the second list to split rides into:
- Group A: start <= finish1 → use prefix min duration to get earliest finish
- Group B: start > finish1 → use suffix min finish time (start immediately)
Optimization Take the minimum finish time over all splits and both orders.

Let's implement this solution in PHP: 3635. Earliest Finish Time for Land and Water Rides II

<?php
/**
 * @param Integer[] $landStartTime
 * @param Integer[] $landDuration
 * @param Integer[] $waterStartTime
 * @param Integer[] $waterDuration
 * @return Integer
 */
function earliestFinishTime(array $landStartTime, array $landDuration, array $waterStartTime, array $waterDuration): int
{
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
echo earliestFinishTime([2,8], [4,1], [6], [3]) . "\n";         // Output: 9
echo earliestFinishTime([5], [3], [1], [10]) . "\n";            // Output: 14
?>

Explanation:

Step 1 – Pair and sort Each ride is stored as [startTime, duration]. Both lists are sorted by start time to allow binary search.
Step 2 – Preprocess second category For water rides (if taken second):
- prefixMinDuration[i] = minimum duration among first i+1 water rides
- suffixMinFinish[i] = minimum finish time among water rides from i to end
- Same preprocessing for land rides when taken second.
Step 3 – Binary search split
- Given finish1 from the first ride, find first index pos where start[pos] > finish1.
- This splits second rides into those starting before/after the end of the first ride.
Step 4 – Compute best finish for this first ride
- For Group A: earliest finish = finish1 + minDuration (start immediately after first ride ends, since all start ≤ finish1)
- For Group B: earliest finish = minFinish[pos] (start at their own start time, since first ride ended earlier)
- Take the smaller of these two as the best for this pairing.
Step 5 – Minimize over all first rides and both orders Track the global minimum finish time.

Complexity

Time Complexity: O(n log n + m log m) for sorting, plus O(n log m + m log n) for binary search per first ride → O((n + m) * log(n + m))
Space Complexity: O(n + m) for storing arrays of start times, durations, finish times, prefix/suffix arrays.

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

3633. Earliest Finish Time for Land and Water Rides I

MD ARIFUL HAQUE — Tue, 02 Jun 2026 17:32:57 +0000

3633. Earliest Finish Time for Land and Water Rides I

Difficulty: Easy

Topics: Mid Level, Array, Two Pointers, Binary Search, Greedy, Sorting, Biweekly Contest 162

You are given two categories of theme park attractions: land rides and water rides.

Land rides
- landStartTime[i] – the earliest time the ith land ride can be boarded.
- landDuration[i] – how long the ith land ride lasts.
Water rides
- waterStartTime[j] – the earliest time the jth water ride can be boarded.
- waterDuration[j] – how long the jth water ride lasts.

A tourist must experience exactly one ride from each category, in either order.

A ride may be started at its opening time or any later moment.
If a ride is started at time t, it finishes at time t + duration.
Immediately after finishing one ride the tourist may board the other (if it is already open) or wait until it opens.

Return the earliest possible time at which the tourist can finish both rides.

Example 1:

Input: landStartTime = [2,8], landDuration = [4,1], waterStartTime = [6], waterDuration = [3]
Output: 9
Explanation:
- Plan A (land ride 0 → water ride 0):
  - Start land ride 0 at time landStartTime[0] = 2. Finish at 2 + landDuration[0] = 6.
  - Water ride 0 opens at time waterStartTime[0] = 6. Start immediately at 6, finish at 6 + waterDuration[0] = 9.
- Plan B (water ride 0 → land ride 1):
  - Start water ride 0 at time waterStartTime[0] = 6. Finish at 6 + waterDuration[0] = 9.
  - Land ride 1 opens at landStartTime[1] = 8. Start at time 9, finish at 9 + landDuration[1] = 10.
- Plan C (land ride 1 → water ride 0):
  - Start land ride 1 at time landStartTime[1] = 8. Finish at 8 + landDuration[1] = 9.
  - Water ride 0 opened at waterStartTime[0] = 6. Start at time 9, finish at 9 + waterDuration[0] = 12.
- Plan D (water ride 0 → land ride 0):
  - Start water ride 0 at time waterStartTime[0] = 6. Finish at 6 + waterDuration[0] = 9.
  - Land ride 0 opened at landStartTime[0] = 2. Start at time 9, finish at 9 + landDuration[0] = 13.
- Plan A gives the earliest finish time of 9.

Example 2:

Input: landStartTime = [5], landDuration = [3], waterStartTime = [1], waterDuration = [10]
Output: 14
Explanation:
- Plan A (water ride 0 → land ride 0):
  - Start water ride 0 at time waterStartTime[0] = 1. Finish at 1 + waterDuration[0] = 11.
  - Land ride 0 opened at landStartTime[0] = 5. Start immediately at 11 and finish at 11 + landDuration[0] = 14.
- Plan B (land ride 0 → water ride 0):
  - Start land ride 0 at time landStartTime[0] = 5. Finish at 5 + landDuration[0] = 8.
  - Water ride 0 opened at waterStartTime[0] = 1. Start immediately at 8 and finish at 8 + waterDuration[0] = 18.
- Plan A provides the earliest finish time of 14.

Constraints:

1 <= n, m <= 100
landStartTime.length == landDuration.length == n
waterStartTime.length == waterDuration.length == m
1 <= landStartTime[i], landDuration[i], waterStartTime[j], waterDuration[j] <= 1000

Hint:

Use brute force

Solution:

The problem requires calculating the earliest possible finish time after riding exactly one land ride and one water ride, in either order, with start times that may be delayed until the ride opens. The solution uses brute‑force iteration over all pairs of rides, computes both possible orders for each pair, and tracks the minimum finish time.

Approach:

Iterate through every combination of a land ride and a water ride.
For each pair, compute the finish time for both sequences:
1. Land first → then water.
2. Water first → then land.
The start time of the second ride is the maximum of the finish time of the first ride and the start time of the second ride (must wait if it isn’t open yet).
Keep the global minimum finish time across all pairs and orders.

Let's implement this solution in PHP: 3633. Earliest Finish Time for Land and Water Rides I

<?php
/**
 * @param Integer[] $landStartTime
 * @param Integer[] $landDuration
 * @param Integer[] $waterStartTime
 * @param Integer[] $waterDuration
 * @return Integer
 */
function earliestFinishTime(array $landStartTime, array $landDuration, array $waterStartTime, array $waterDuration): int
{
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
echo earliestFinishTime([2,8], [4,1], [6], [3]) . "\n";         // Output: 9
echo earliestFinishTime([5], [3], [1], [10]) . "\n";            // Output: 14
?>

Explanation:

The brute‑force method is feasible because the number of rides in each category is at most 100, so checking all (n × m) pairs is fine.
For each pair (land[i], water[j]):
- Land first:
  - Land finishes at landStartTime[i] + landDuration[i].
  - Water starts at max(landFinishTime, waterStartTime[j]).
  - Water finishes at waterStart + waterDuration[j].
- Water first:
  - Water finishes at waterStartTime[j] + waterDuration[j].
  - Land starts at max(waterFinishTime, landStartTime[i]).
  - Land finishes at landStart + landDuration[i].
The answer is the smallest finish time from all orders and all pairs.

Complexity

Time Complexity: O(n × m) — loops through all land–water pairs, each with constant work.
Space Complexity: O(1) — only a few scalar variables used, independent of input size.

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

2144. Minimum Cost of Buying Candies With Discount

MD ARIFUL HAQUE — Mon, 01 Jun 2026 16:21:16 +0000

2144. Minimum Cost of Buying Candies With Discount

Difficulty: Easy

Topics: Mid Level, Array, Greedy, Sorting, Biweekly Contest 70

A shop is selling candies at a discount. For every two candies sold, the shop gives a third candy for free.

The customer can choose any candy to take away for free as long as the cost of the chosen candy is less than or equal to the minimum cost of the two candies bought.

For example, if there are 4 candies with costs 1, 2, 3, and 4, and the customer buys candies with costs 2 and 3, they can take the candy with cost 1 for free, but not the candy with cost 4.

Given a 0-indexed integer array cost, where cost[i] denotes the cost of the iᵗʰ candy, return the minimum cost of buying all the candies.

Example 1:

Input: cost = [1,2,3]
Output: 5
Explanation:
- We buy the candies with costs 2 and 3, and take the candy with cost 1 for free.
- The total cost of buying all candies is 2 + 3 = 5. This is the only way we can buy the candies.
- Note that we cannot buy candies with costs 1 and 3, and then take the candy with cost 2 for free.
- The cost of the free candy has to be less than or equal to the minimum cost of the purchased candies.

Example 2:

Input: cost = [6,5,7,9,2,2]
Output: 23
Explanation:
- The way in which we can get the minimum cost is described below:
- Buy candies with costs 9 and 7
- Take the candy with cost 6 for free
- We buy candies with costs 5 and 2
- Take the last remaining candy with cost 2 for free
- Hence, the minimum cost to buy all candies is 9 + 7 + 5 + 2 = 23.

Example 3:

Input: cost = [5,5]
Output: 10
Explanation:
- Since there are only 2 candies, we buy both of them. There is not a third candy we can take for free.
- Hence, the minimum cost to buy all candies is 5 + 5 = 10.

Constraints:

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

Hint:

If we consider costs from high to low, what is the maximum cost of a single candy that we can get for free?
How can we generalize this approach to maximize the costs of the candies we get for free?
Can “sorting” the array help us find the minimum cost?

Solution:

The solution reduces total cost by sorting candy prices in descending order and taking every third candy for free, because the discount allows a free candy whose price is ≤ the cheaper of the two purchased candies. Sorting descending and skipping every third item maximizes the value of free candies.

Approach:

Sort the array in descending order so the most expensive candies are considered first.
Iterate through the sorted list, adding the cost of each candy to the total except for every third candy.
The index pattern (0, 1, 3, 4, 6, 7, …) ensures that after buying two candies, the next one is free.
Sum all purchased candies and return the total.

Let's implement this solution in PHP: 2144. Minimum Cost of Buying Candies With Discount

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

// Test cases
echo minimumCost([1,2,3]) . "\n";               // Output: 5
echo minimumCost([6,5,7,9,2,2]) . "\n";         // Output: 23
echo minimumCost([5,5]) . "\n";                 // Output: 10
?>

Explanation:

Sorting descending ensures that when we take a free candy, it’s the smallest possible among the remaining items.
Index check (i % 3 != 2) means we skip adding the price for the third candy in every group of three.
Example: costs sorted → 9, 7, 6, 5, 2, 2
- Buy 9 (index 0), buy 7 (index 1), skip 6 (index 2), buy 5 (index 3), buy 2 (index 4), skip 2 (index 5)
- Total = 9 + 7 + 5 + 2 = 23
This greedy method works because taking a free candy from the smallest available prices is always optimal.

Complexity

Time Complexity: O(n log n) — due to sorting.
Space Complexity: O(1) — ignoring the input storage, 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

2126. Destroying Asteroids

MD ARIFUL HAQUE — Sun, 31 May 2026 17:40:45 +0000

2126. Destroying Asteroids

Difficulty: Medium

Topics: Staff, Array, Greedy, Sorting, Weekly Contest 274

You are given an integer mass, which represents the original mass of a planet. You are further given an integer array asteroids, where asteroids[i] is the mass of the iᵗʰ asteroid.

You can arrange for the planet to collide with the asteroids in any arbitrary order. If the mass of the planet is greater than or equal to the mass of the asteroid, the asteroid is destroyed and the planet gains the mass of the asteroid. Otherwise, the planet is destroyed.

Return true if all asteroids can be destroyed. Otherwise, return false.

Example 1:

Input: mass = 10, asteroids = [3,9,19,5,21]
Output: true
Explanation:
- One way to order the asteroids is [9,19,5,3,21]:
- The planet collides with the asteroid with a mass of 9. New planet mass: 10 + 9 = 19
- The planet collides with the asteroid with a mass of 19. New planet mass: 19 + 19 = 38
- The planet collides with the asteroid with a mass of 5. New planet mass: 38 + 5 = 43
- The planet collides with the asteroid with a mass of 3. New planet mass: 43 + 3 = 46
- The planet collides with the asteroid with a mass of 21. New planet mass: 46 + 21 = 67
- All asteroids are destroyed.

Example 2:

Input: mass = 5, asteroids = [4,9,23,4]
Output: false
Explanation:
- The planet cannot ever gain enough mass to destroy the asteroid with a mass of 23.
- After the planet destroys the other asteroids, it will have a mass of 5 + 4 + 9 + 4 = 22.
- This is less than 23, so a collision would not destroy the last asteroid.

Constraints:

1 <= mass <= 10⁵
1 <= asteroids.length <= 10⁵
1 <= asteroids[i] <= 10⁵

Hint:

Choosing the asteroid to collide with can be done greedily.
If an asteroid will destroy the planet, then every bigger asteroid will also destroy the planet.
You only need to check the smallest asteroid at each collision. If it will destroy the planet, then every other asteroid will also destroy the planet.
Sort the asteroids in non-decreasing order by mass, then greedily try to collide with the asteroids in that order.

Solution:

The solution determines whether a planet with a given starting mass can destroy all asteroids by colliding with them in an optimal order.

It does this by sorting the asteroids in ascending order and then greedily absorbing them one by one, ensuring the planet’s mass never drops below the next asteroid’s mass. If at any point the planet’s mass is insufficient, the answer is false; otherwise, it’s true.

Approach:

Sorting the asteroids in non-decreasing order ensures we always try to absorb the smallest possible asteroid next.
Greedy absorption — if the planet’s current mass is at least the asteroid’s mass, it absorbs it and increases its mass.
Early exit — if at any step the planet’s mass is less than the asteroid’s mass, all larger asteroids will also be impossible to absorb, so we return false.
Final check — if all asteroids are processed successfully, return true.

Let's implement this solution in PHP: 2126. Destroying Asteroids

<?php
/**
 * @param Integer $mass
 * @param Integer[] $asteroids
 * @return Boolean
 */
function asteroidsDestroyed(int $mass, array $asteroids): bool
{
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
echo asteroidsDestroyed([1, 2, 3, 10, 4, 2, 3, 5]) . "\n";      // Output: true
echo asteroidsDestroyed([5, 4, 3, 2, 1]) . "\n";                // Output: false
?>

Explanation:

Step 1: Sort the asteroids array so the smallest asteroids come first.

Reason: Absorbing smaller asteroids first maximizes the chance of reaching a mass large enough to take on bigger ones.
Step 2: Initialize currentMass with the planet’s starting mass.

Purpose: Track the planet’s mass dynamically as it absorbs asteroids.
Step 3: Loop through each asteroid in the sorted list.

Check: If currentMass >= asteroid, the planet can destroy it — add the asteroid’s mass to currentMass.

Otherwise: Immediately return false (planet is destroyed).
Step 4: If the loop completes without returning false, return true (all asteroids destroyed).

Complexity

Time Complexity: O(n log n) due to sorting, where n is the number of asteroids. Greedy traversal is O(n).
Space Complexity: O(1) extra space (sorting may use O(log n) stack space in PHP’s sort() function).

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

3161. Block Placement Queries

MD ARIFUL HAQUE — Sun, 31 May 2026 15:00:00 +0000

3161. Block Placement Queries

Difficulty: Hard

Topics: Principal, Array, Binary Search, Binary Indexed Tree, Segment Tree, Biweekly Contest 131

There exists an infinite number line, with its origin at 0 and extending towards the positive x-axis.

You are given a 2D array queries, which contains two types of queries:

For a query of type 1, queries[i] = [1, x]. Build an obstacle at distance x from the origin. It is guaranteed that there is no obstacle at distance x when the query is asked.
For a query of type 2, queries[i] = [2, x, sz]. Check if it is possible to place a block of size sz anywhere in the range [0, x] on the line, such that the block entirely lies in the range [0, x]. A block cannot be placed if it intersects with any obstacle, but it may touch it. Note that you do not actually place the block. Queries are separate.

Return a boolean array results, where results[i] is true if you can place the block specified in the iᵗʰ query of type 2, and false otherwise.

Example 1:

Input: queries = [[1,2],[2,3,3],[2,3,1],[2,2,2]]
Output: [false,true,true]
Explanation: For query 0, place an obstacle at x = 2. A block of size at most 2 can be placed before x = 3.

Example 2:

Input: queries = [[1,7],[2,7,6],[1,2],[2,7,5],[2,7,6]]
Output: [true,true,false]
Explanation:
- Place an obstacle at x = 7 for query 0. A block of size at most 7 can be placed before x = 7.
- Place an obstacle at x = 2 for query 2. Now, a block of size at most 5 can be placed before x = 7, and a block of size at most 2 before x = 2.

Constraints:

1 <= queries.length <= 15 * 10⁴
2 <= queries[i].length <= 3
1 <= queries[i][0] <= 2
1 <= x, sz <= min(5 * 10⁴, 3 * queries.length)
The input is generated such that for queries of type 1, no obstacle exists at distance x when the query is asked.
The input is generated such that there is at least one query of type 2.

Hint:

Let d[x] be the distance of the next obstacle after x.
For each query of type 2, we just need to check if max(d[0], d[1], d[2], …d[x - sz]) > sz.
Use segment tree to maintain d[x].

Solution:

The problem involves handling two types of queries on an infinite positive number line:

Type 1: Place an obstacle at a given coordinate.
Type 2: Check if a block of a given size can fit entirely within a range [0, x] without intersecting any obstacles (touching is allowed).

The solution uses a segment tree to maintain the largest gap starting at each position between obstacles, and a sorted list of obstacles to efficiently update and query gaps. It answers each query in O(log n) time.

Approach:

Segment tree stores, for each position i, the size of the gap starting at i (i.e., the distance to the next obstacle to the right).
Obstacles list is kept sorted to allow binary search for predecessor and successor.
Sentinel obstacle at 0 simplifies gap tracking.
For type 2 queries, we first check the partial gap from the last obstacle to x. If that fits, answer is true. Otherwise, we query the segment tree for the maximum gap starting anywhere in [0, x - sz].
For type 1 queries, we find predecessor and successor obstacles, update the gaps for both ends, and insert the new obstacle into the sorted list.

Let's implement this solution in PHP: 3161. Block Placement Queries

<?php
/**
 * @param Integer[][] $queries
 * @return Boolean[]
 */
function getResults(array $queries): array
{
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
echo getResults([[1,2],[2,3,3],[2,3,1],[2,2,2]]) . "\n";                // Output: [false,true,true]
echo getResults([[1,7],[2,7,6],[1,2],[2,7,5],[2,7,6]]) . "\n";          // Output: [true,true,false]
?>

Explanation:

Initialization: Start with obstacle at 0 and a large initial gap from 0 to maxVal (an upper bound slightly larger than any given coordinate).
Type 1 (add obstacle at p):
- Find predecessor L and successor R using binary search on sorted obstacles list.
- Update segment tree at L with new gap p - L.
- Update segment tree at p with new gap R - p.
- Insert p into sorted obstacles.
Type 2 (query for sz in [0, x]):
- If sz > x, immediately return false.
- Find last obstacle lastObs ≤ x using binary search.
- If x - lastObs ≥ sz, return true (fits in rightmost gap).
- Otherwise, query segment tree for max gap in [0, x - sz]. If that max gap ≥ sz, return true, else false.
Segment tree operations:
- set(idx, val) updates position idx with new gap size.
- max(l, r) returns largest gap size in range [l, r].

Complexity

Time Complexity:
- Type 1: Binary search + segment tree updates → O(log n)
- Type 2: Binary search + segment tree query → O(log n)
- Total: O(q log n) where q is number of queries, n is range size.
Space Complexity:
- Segment tree: O(n)
- Obstacles list: O(q)
- Total: O(n + q) where n = maxVal.

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

3300. Minimum Element After Replacement With Digit Sum

MD ARIFUL HAQUE — Fri, 29 May 2026 16:44:19 +0000

3300. Minimum Element After Replacement With Digit Sum

Difficulty: Easy

Topics: Mid Level, Array, Math, Biweekly Contest 140

You are given an integer array nums.

You replace each element in nums with the sum of its digits.

Return the minimum element in nums after all replacements.

Example 1:

Input: nums = [10,12,13,14]
Output: 1
Explanation: nums becomes [1, 3, 4, 5] after all replacements, with minimum element 1.

Example 2:

Input: nums = [1,2,3,4]
Output: 1
Explanation: nums becomes [1, 2, 3, 4] after all replacements, with minimum element 1.

Example 3:

Input: nums = [999,19,199]
Output: 10
Explanation: nums becomes [27, 10, 19] after all replacements, with minimum element 10.

Constraints:

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

Hint:

Convert to string and calculate the sum for each element.

Solution:

The solution replaces each element in the array with the sum of its digits, then returns the smallest resulting value. This is done without storing the transformed array, keeping memory usage low.

Approach:

Iterate through each number in the input array.
Compute the digit sum for the current number.
Track the minimum digit sum found so far.
Return the minimum value after processing all numbers.

Let's implement this solution in PHP: 3300. Minimum Element After Replacement With Digit Sum

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

// Test cases
echo minElement([10,12,13,14]) . "\n";          // Output: 1
echo minElement([1,2,3,4]) . "\n";              // Output: 1
echo minElement([999,19,199]) . "\n";           // Output: 10
?>

Explanation:

Digit sum calculation is performed using repeated modulus and integer division.
No auxiliary array is created — only the running minimum is stored.
Comparison and update happen in the same loop, making the solution efficient.

Complexity

Time Complexity: O(n * d) — where n is the array length and d is the number of digits in the largest number (max 5 digits since nums[i] ≤ 10⁴).
Space Complexity: O(1) — only a few integer 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

3093. Longest Common Suffix Queries

MD ARIFUL HAQUE — Thu, 28 May 2026 16:46:39 +0000

3093. Longest Common Suffix Queries

Difficulty: Hard

Topics: Senior Staff, Array, String, Trie, Weekly Contest 390

You are given two arrays of strings wordsContainer and wordsQuery.

For each wordsQuery[i], you need to find a string from wordsContainer that has the longest common suffix with wordsQuery[i]. If there are two or more strings in wordsContainer that share the longest common suffix, find the string that is the smallest in length. If there are two or more such strings that have the same smallest length, find the one that occurred earlier in wordsContainer.

Return an array of integers ans, where ans[i] is the index of the string in wordsContainer that has the longest common suffix with wordsQuery[i].

Example 1:

Input: wordsContainer = ["abcd","bcd","xbcd"], wordsQuery = ["cd","bcd","xyz"]
Output: [1,1,1]
Explanation:
- Let's look at each wordsQuery[i] separately:
  - For wordsQuery[0] = "cd", strings from wordsContainer that share the longest common suffix "cd" are at indices 0, 1, and 2. Among these, the answer is the string at index 1 because it has the shortest length of 3.
  - For wordsQuery[1] = "bcd", strings from wordsContainer that share the longest common suffix "bcd" are at indices 0, 1, and 2. Among these, the answer is the string at index 1 because it has the shortest length of 3.
  - For wordsQuery[2] = "xyz", there is no string from wordsContainer that shares a common suffix. Hence the longest common suffix is "", that is shared with strings at index 0, 1, and 2. Among these, the answer is the string at index 1 because it has the shortest length of 3.

Example 2:

Input: wordsContainer = ["abcdefgh","poiuygh","ghghgh"], wordsQuery = ["gh","acbfgh","acbfegh"]
Output: [2,0,2]
Explanation:
- Let's look at each wordsQuery[i] separately:
  - For wordsQuery[0] = "gh", strings from wordsContainer that share the longest common suffix "gh" are at indices 0, 1, and 2. Among these, the answer is the string at index 2 because it has the shortest length of 6.

Constraints:

1 <= wordsContainer.length, wordsQuery.length <= 10⁴
1 <= wordsContainer[i].length <= 5 * 10³
1 <= wordsQuery[i].length <= 5 * 10³
wordsContainer[i] consists only of lowercase English letters.
wordsQuery[i] consists only of lowercase English letters.
Sum of wordsContainer[i].length is at most 5 * 1⁵.
Sum of wordsQuery[i].length is at most 5 * 10⁵.

Hint:

If we reverse the strings, the problem changes to finding the longest common prefix.
Build a Trie, each node is a letter and only saves the best word’s index in each node, based on the criteria.

Solution:

The problem requires finding, for each query string, the index of a container string that shares the longest common suffix with the query.

Tie-breaking rules:

Prefer the shortest string among those with the longest common suffix.
If lengths are equal, prefer the earliest index in wordsContainer.

The solution reverses all strings and builds a trie on the reversed container strings, storing the best (shortest length, earliest index) string at each node.

Each query is reversed and traversed in the trie; the last reachable node gives the best container index.

Approach:

Reverse strings to convert the problem into a longest common prefix problem in a trie.
Build a trie from reversed container strings.
Store in each trie node the best container word index based on:
- Primary: shortest length of original word
- Secondary: smallest index if lengths are equal
Process each query by reversing it and walking the trie as far as possible.
The best index at the final node is the answer.

Let's implement this solution in PHP: 3093. Longest Common Suffix Queries

<?php
/**
 * @param String[] $wordsContainer
 * @param String[] $wordsQuery
 * @return Integer[]
 */
function stringIndices(array $wordsContainer, array $wordsQuery): array
{
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}


// Test cases
echo stringIndices(["abcd","bcd","xbcd"], ["cd","bcd","xyz"]) . "\n";                           // Output: [1,1,1]
echo stringIndices(["abcdefgh","poiuygh","ghghgh"], ["gh","acbfgh","acbfegh"]) . "\n";          // Output: [2,0,2]
?>

Explanation:

Step 1 — Reverse strings Reversing turns "longest common suffix" into "longest common prefix" in a trie.
Step 2 — Initialize trie and root node Root node’s best index/length are updated from all container words, since an empty suffix is always valid.
Step 3 — Insert each container word (reversed) into trie
- At each node (including root), check if the current word’s length is shorter than stored best length, or equal length but earlier index → update best.
- This ensures later queries can quickly get the best match for any prefix.
Step 4 — Query processing
- Reverse query string, walk down trie character by character.
- Stop when a character is missing in children.
- The last successfully reached node’s stored best index is the answer.
Step 5 — Complexity handling Total container + query length is large (up to ~5×10⁵), so trie traversal is efficient.

Complexity

Time Complexity:
- Building trie: O(∑ |wordsContainer[i]|)
- Query processing: O(∑ |wordsQuery[i]|)
- Total: O(total length of all strings)
Space Complexity:
- Trie nodes: O(∑ |wordsContainer[i]|)
- Each node stores children map and two integers.
- Total: O(total length of all container strings)

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

3121. Count the Number of Special Characters II

MD ARIFUL HAQUE — Wed, 27 May 2026 15:36:29 +0000

3121. Count the Number of Special Characters II

Difficulty: Medium

Topics: Senior, Hash Table, String, Weekly Contest 394

You are given a string word. A letter c is called special if it appears both in lowercase and uppercase in word, and every lowercase occurrence of c appears before the first uppercase occurrence of c.

Return the number of special letters in word.

Example 1:

Input: word = "aaAbcBC"
Output: 3
Explanation: The special characters are 'a', 'b', and 'c'.

Example 2:

Input: word = "abc"
Output: 0
Explanation: There are no special characters in word.

Example 3:

Input: "AbBCab"
Output: [0,1]
Explanation: There are no special characters in word.

Constraints:

1 <= word.length <= 2 * 10⁵
word consists of only lowercase and uppercase English letters.

Hint:

For each character c, store the first occurrence of its uppercase and the last occurrence of its lowercase.

Solution:

The problem requires counting letters that appear in both lowercase and uppercase forms in a string, with the constraint that every lowercase occurrence of a letter must appear before the first uppercase occurrence of the same letter.

The solution tracks the first occurrence of each uppercase letter and the last occurrence of each lowercase letter, then compares their indices.

Approach:

Use two arrays to store the first occurrence index of uppercase letters and the last occurrence index of lowercase letters.
Iterate through the string once, updating these arrays.
For each letter a..z, check if:
- Both its lowercase and uppercase forms exist in the string.
- The last lowercase occurrence occurs before the first uppercase occurrence.
If both conditions are met, count it as a special character.

Let's implement this solution in PHP: 3121. Count the Number of Special Characters II

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

// Test cases
echo numberOfSpecialChars("aaAbcBC") . "\n";        // Output: 3
echo numberOfSpecialChars("abc") . "\n";            // Output: 0
echo numberOfSpecialChars("AbBCab") . "\n";         // Output: 0
?>

Explanation:

first array stores the first occurrence index for each character (both cases).
last array stores the last occurrence index for each character.
During traversal:
- If a character hasn’t been seen before, set first[char] to current index.
- Always update last[char] to current index.
After traversal, check each lowercase letter i:
- last['a' + i] → last index of lowercase.
- first['A' + i] → first index of uppercase.
- Condition: last[lower] < first[upper] ensures all lowercase occur before any uppercase.
Count how many satisfy this.

Complexity

Time Complexity: O(n) — single pass through the string, then O(26) for checking letters.
Space Complexity: O(1) — fixed-size arrays for ASCII characters.

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

3120. Count the Number of Special Characters I

MD ARIFUL HAQUE — Tue, 26 May 2026 16:30:47 +0000

3120. Count the Number of Special Characters I

Difficulty: Easy

Topics: Mid Level, Hash Table, String, Weekly Contest 394

You are given a string word. A letter is called special if it appears both in lowercase and uppercase in word.

Return the number of special letters in word.

Example 1:

Input: word = "aaAbcBC"
Output: 3
Explanation: The special characters in word are 'a', 'b', and 'c'.

Example 2:

Input: word = "abc"
Output: 0
Explanation: No character in word appears in uppercase.

Example 3:

Input: word = "abBCab"
Output: 1
Explanation: The only special character in word is 'b'.

Constraints:

1 <= word.length <= 50
word consists of only lowercase and uppercase English letters.

Hint:

The constraints are small. For all 52 characters, check if they are present in word.

Solution:

The solution determines how many English letters appear in both lowercase and uppercase forms within a given string. It uses two boolean arrays to track the presence of each letter (a–z) in lowercase and uppercase separately, then counts the letters that appear in both arrays.

Approach:

Track lowercase and uppercase letters separately using two fixed-size boolean arrays (size 26).
Iterate through the string and mark the appropriate array based on whether the character is lowercase or uppercase.
Count matches by checking both arrays for the same letter index.

Let's implement this solution in PHP: 3120. Count the Number of Special Characters I

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

// Test cases
echo numberOfSpecialChars("aaAbcBC") . "\n";            // Output: 3
echo numberOfSpecialChars("abc") . "\n";                // Output: 0
echo numberOfSpecialChars("abBCab") . "\n";             // Output: 1
?>

Explanation:

Initialize two arrays $lower and $upper of size 26, all set to false. Index 0 represents 'a'/'A', index 1 represents 'b'/'B', etc.
Loop through each character in the string:
- If the character is lowercase, mark $lower[index] = true.
- If the character is uppercase, mark $upper[index] = true.
After processing the string, loop through indexes 0 to 25:
- If both $lower[i] and $upper[i] are true, increment the count.
Return the total count of special characters.

Complexity

Time Complexity: O(n), One pass through the string (n = length of word) and one pass through the 26 letters → O(n + 26) → O(n).
Space Complexity: O(1), Two fixed-size arrays of 26 booleans → constant 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