Algorithm - LeetCode Problems 4

Problem 2784. Check if Array is Good

• You are given an integer array nums. We consider an array good if it is a permutation of an array base[n].

• base[n] = [1, 2, ..., n - 1, n, n] (in other words, it is an array of length n + 1 which contains 1 to n - 1 exactly once, plus two occurrences of n). For example, base[1] = [1, 1] and base[3] = [1, 2, 3, 3].

• Return true if the given array is good, otherwise return false.

• Note: A permutation of integers represents an arrangement of these numbers.

Examples

• Example 1:

  • Input: nums = [2, 1, 3]
  • Output: false
  • Explanation:
    • Since the maximum element of the array is 3, the only candidate n for which this array could be a permutation of base[n], is n = 3.
    • However, base[3] has four elements but array nums has three. Therefore, it can not be a permutation of base[3] = [1, 2, 3, 3].
    • So the answer is false.

• Example 2:

  • Input: nums = [1, 3, 3, 2]
  • Output: true
  • Explanation:
    • Since the maximum element of the array is 3, the only candidate n for which this array could be a permutation of base[n], is n = 3.
    • It can be seen that nums is a permutation of base[3] = [1, 2, 3, 3] (by swapping the second and fourth elements in nums, we reach base[3]).
    • Therefore, the answer is true.

• Example 3:

  • Input: nums = [3, 4, 4, 1, 2, 1]
  • Output: false
  • Explanation:
    • Since the maximum element of the array is 4, the only candidate n for which this array could be a permutation of base[n], is n = 4.
    • However, base[4] has five elements but array nums has six. Therefore, it can not be a permutation of base[4] = [1, 2, 3, 4, 4].
    • So the answer is false.

Constraints:

• 1 <= nums.length <= 100
• 1 <= num[i] <= 200

Solution

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var isGood = function(nums) {
    const length = nums.length;
    nums.sort((a, b) => a - b);
    
    if (nums[length - 1] !== nums[length - 2]) {
        return false;
    }

    let number = 1;
    for (let i = 0; i < length - 1; i++) {
        if (nums[i] !== number) {
            return false;
        }
        number++;
    }

    return true;
};

Problem 46. Permutations

• Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.

Examples

• Example 1:

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

• Example 2:

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

Constraints:

• 1 <= nums.length <= 6
• -10 <= nums[i] <= 10
• All the integers of nums are unique.

Solution

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permute = function(nums) {
    const answer = [];
    
    const dfs = (permutation, rest) => {
        if (!rest.length) {
            answer.push(permutation);
            return;
        }

        for (let i = 0; i < rest.length; i++) {
            dfs([...permutation, rest[i]], [...rest.slice(0, i), ...rest.slice(i+1)]);
        }
    };

    dfs([], nums);
    
    return answer;
};

Problem 2089. Find Target Indices After Sorting Array

• You are given a 0-indexed integer array nums and a target element target.

• A target index is an index i such that nums[i] == target.

• Return a list of the target indices of nums after sorting nums in non-decreasing order. If there are no target indices, return an empty list.

  • The returned list must be sorted in increasing order.

Examples

• Example 1:

  • Input: nums = [1,2,5,2,3], target = 2
  • Output: [1,2]
  • Explanation:
    • After sorting, nums is [1,2,2,3,5].\
    • The indices where nums[i] == 2 are 1 and 2.

• Example 2

  • Input: nums = [1,2,5,2,3], target = 3
  • Output: [3]
  • Explanation:
    • After sorting, nums is [1,2,2,3,5].
    • The index where nums[i] == 3 is 3.

Constraints:

• 1 <= nums.length <= 100
• 1 <= nums[i], target <= 100

Solution

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var targetIndices = function(nums, target) {
    const answer = [];

    if (!nums.includes(target)) {
        return answer;
    }

    nums.sort((a, b) => a - b);

    const binarySearch = (start, end) => {
        if (start > end) {
            return;
        }

        const middle = Math.floor((start + end)/2);

        if (nums[middle] === target) {
            answer.push(middle);
        }

        binarySearch(start, middle - 1);
        binarySearch(middle + 1, end);
    }

    binarySearch(0, nums.length - 1);

    return answer.sort((a, b) => a - b);
};