algoadvance

Leetcode 491. Non

Problem Statement:

Given an integer array nums, return all the different possible non-decreasing subsequences of the given array with at least two elements. You may return the answer in any order.

Clarifying Questions:

  1. Can elements in the subsequence be repeated?
    • Yes, the elements can be repeated.
  2. Do we need to check for strictly increasing subsequences only?
    • No, the subsequence should be non-decreasing, which means it can contain duplicates but always in non-decreasing order.
  3. Are there any constraints on the length of the input array?
    • Yes, 1 <= nums.length <= 15 and -100 <= nums[i] <= 100.
  4. How are the results supposed to be returned?
    • As a list of lists, where each list is a non-decreasing subsequence.

Strategy:

  1. Backtracking: This approach is suitable because it allows us to explore all possible subsequences and make decisions at each step.
    • We’ll use a helper function that will recursively build subsequences.
    • Use a set to avoid duplicate subsequences.
  2. Use Parameters Efficiently:
    • Start with an empty list to accumulate the current subsequence.
    • Use an index to track the next position to consider in the array.
  3. Base Case:
    • If the accumulating list has at least two elements, add it to the result set.
  4. Recursive Case:
    • Iterate through the remaining array elements.
    • If an element can be appended to the current subsequence (to maintain the non-decreasing property), make a recursive call with the updated list and index.
    • Skip duplicate elements in the same recursive level to avoid redundant work.

Code:

import java.util.*;

public class Solution {
    public List<List<Integer>> findSubsequences(int[] nums) {
        Set<List<Integer>> result = new HashSet<>();
        List<Integer> tempList = new ArrayList<>();
        backtrack(result, tempList, nums, 0);
        return new ArrayList<>(result);
    }

    private void backtrack(Set<List<Integer>> result, List<Integer> tempList, int[] nums, int start) {
        if (tempList.size() >= 2) {
            result.add(new ArrayList<>(tempList));
        }

        for (int i = start; i < nums.length; i++) {
            if (tempList.isEmpty() || nums[i] >= tempList.get(tempList.size() - 1)) {
                tempList.add(nums[i]);
                backtrack(result, tempList, nums, i + 1);
                tempList.remove(tempList.size() - 1);
            }
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = {4, 6, 7, 7};
        System.out.println(solution.findSubsequences(nums));
    }
}

Time Complexity:

This solution efficiently finds all non-decreasing subsequences by exploring all potential subsequences through a backtracking approach. The usage of a set ensures that duplicate subsequences are filtered out.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI