We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Flatten Deeply Nested Array

Difficulty: Medium

Problem Description

Given a multi-dimensional array arr and a depth n, return a flattened version of that array. A multi-dimensional array is a recursive data structure that contains integers or other multi-dimensional arrays. A flattened array is a version of that array with some or all of the sub-arrays removed and replaced with the actual elements in that sub-array. This flattening operation should only be done if the current depth of nesting is less than n. The depth of the elements in the first array are considered to be 0.

Key Insights

  • The input array can contain integers and nested arrays of varying depths.
  • Flattening only occurs for sub-arrays at a depth less than n.
  • The recursion or iterative approach can be employed to traverse and flatten the array.
  • Maintaining the current depth during traversal is crucial to determine when to flatten.

Space and Time Complexity

Time Complexity: O(m), where m is the total number of elements in the array (including nested arrays). Space Complexity: O(m), as we may need to store all elements in a new array in the worst case.

Solution

To solve the problem, we can use a recursive approach. We will define a function that takes the current array and the current depth as parameters. If the current depth is less than n, we will iterate through the elements of the array. If an element is an integer, we add it to the result. If it's a sub-array, we recursively call the function to flatten it. Otherwise, we add the sub-array as is. This way, we manage to flatten only the required levels of the array while maintaining the others intact.

Code Solutions

def flatten(arr, n):
    def helper(sub_arr, depth):
        if depth >= n:
            return [sub_arr]  # Return as is if at or above the depth
        result = []
        for item in sub_arr:
            if isinstance(item, list):
                result.extend(helper(item, depth + 1))  # Recur for nested arrays
            else:
                result.append(item)  # Add integers directly
        return result

    return helper(arr, 0)  # Start with depth 0
← Back to All Questions