[Leetcode] 2727. Is Object Empty

ways! — Wed, 02 Oct 2024 13:39:20 +0000

Question Link: https://leetcode.com/problems/is-object-empty/description/

[Problem Statment]

Given an object or an array, return if it is empty.

An empty object contains no key-value pairs.
An empty array contains no elements.

You may assume the object or array is the output of JSON.parse.

[Understanding Question]

Sooo... we’re getting either an Array or an Object as the parameter to this function called obj. (Yeah, I know, super creative name, but it'll make sense later!)
Our task? Perform some magic coding tricks to first figure out if this obj is an array or an object. Then, based on that knowledge, we’ll decide what to do next.
Finally, we need to check if this object/array is empty or not. Simple, right? (Or is it...)

[Key Points]

First things first: "An array is technically an object in JavaScript." Yep! That’s right—arrays are a special type of object in JS. So, don't get confused!
Object Detection 101: We can check if the parameter is actually an object (or array) by using typeof obj === 'object' && obj !== null. Why the !== null part? Well, because null is a special case in JS. Even though it's technically of type object, it's like the empty void of nothingness. So, we exclude that, just in case (even though the problem didn’t explicitly mention it, it’s a good habit).
Undefined and null Elements: Both objects and arrays can have properties/elements that are undefined or null. But no worries—they'll still count when we check the length. They don’t get a free pass from our validation!
Is it an Array?: We can check if the parameter is an array using Array.isArray(obj). No need to check again if it’s an object, though—we already did that earlier.

[Solution Code]

var isEmpty = function (obj) {
  if (typeof obj === "object" && obj !== null) { // Check if it's an object and not null
    if (Array.isArray(obj)) { // If it's an array
      return obj.length === 0; // Return true if it's empty
    } else { // If it's an object
      return Object.keys(obj).length === 0; // Return true if there are no keys
    }
  }
  return false; // If it's neither an object nor an array, return false
};

[Breaking It Down... even further]

Step 1: Check if it’s an object
First, we use typeof obj === 'object' && obj !== null to ensure the input is an object and not null. (Because we all know that typeof null === 'object is one of JavaScript’s weird quirks. Thanks, JavaScript!)

Step 2: Is it an array?
We use Array.isArray(obj) to distinguish between arrays and regular objects. Arrays have a length property, so we can directly check if obj.length === 0.

Step 3: Is it an object?
If it’s not an array, we check if it's an object using Object.keys(obj).length === 0. This method returns the number of keys in the object. No keys? It's empty!

Step 4: Default case
If the input isn’t an object (or it’s null), we return false because the question specifies we're working with either objects or arrays only.

1497. Check If Array Pairs Are Divisible by k

ways! — Tue, 01 Oct 2024 22:07:45 +0000

Question Link : 1497. Check If Array Pairs Are Divisible by k

[Problem Statement]

Given an array of integers arr of even length n and an integer k, we need to determine if it's possible to divide the array into exactly n/2 pairs such that the sum of each pair is divisible by k. The function should return true if such a division is possible, and false otherwise.

Key Insight

The crucial insight that makes this algorithm efficient is based on the properties of modular arithmetic:

If (a + b) % k == 0, then (a % k + b % k) % k == 0.
This means that for two numbers to sum to a multiple of k, their remainders when divided by k must sum to k (or 0, which is the same in modular arithmetic).

Algorithm Steps

Initialize Remainder Count:
- Create an array remainders of length k, initialized with zeros.
- This array will count how many numbers in arr have each possible remainder when divided by k.
Count Remainders:
- Iterate through each number num in the input array arr.
- Calculate its remainder when divided by k using ((num % k) + k) % k.
- Increment the count for this remainder in the remainders array.
Check Pairing Possibility:
- Iterate through the remainders from 0 to k/2: a. For remainder 0 and k/2 (if k is even):
  - Check if the count is even. If not, return false. b. For all other remainders i:
  - Check if the count of remainder i equals the count of remainder k-i.
  - If not, return false.
Return Result:
- If all checks pass, return true.

Detailed Breakdown

Counting Remainders

for (let num of arr) {
    remainders[((num % k) + k) % k]++;
}

We use ((num % k) + k) % k instead of just num % k to handle negative numbers correctly.
This ensures all remainders are in the range [0, k-1].

Checking Pairing Possibility

for (let i = 0; i <= k / 2; i++) {
    if (i === 0 || (k % 2 === 0 && i === k / 2)) {
        if (remainders[i] % 2 !== 0) return false;
    } else {
        if (remainders[i] !== remainders[k - i]) return false;
    }
}

We only need to check up to k/2 because remainders pair symmetrically.
For remainder 0 and k/2 (when k is even), we need an even count because these can only pair with themselves.
For all other remainders i, we need the count of i to equal the count of k-i, as these will pair with each other.

Time and Space Complexity

Time Complexity: O(n + k), where n is the length of arr.
- We iterate through arr once to count remainders: O(n)
- We then iterate through half of k to check pairing: O(k/2)
Space Complexity: O(k) for the remainders array.

Why This Works

By counting remainders, we reduce the problem from checking every possible pair (which would be O(n^2)) to checking if remainders can be paired (which is O(n + k)).
The pairing check ensures that for every number with remainder i, there's a corresponding number with remainder k-i to pair with it, such that their sum is divisible by k.

Edge Cases and Considerations

The algorithm correctly handles negative numbers.
It works for any positive integer k.
It implicitly handles the case where some numbers in arr are already divisible by k (remainder 0).

This algorithm efficiently solves the problem by leveraging properties of modular arithmetic, avoiding the need to actually form the pairs or check every possible pairing.

DEV Community: ways!