List Flattening

List flattening refers to the process of converting a nested list structure containing sublists into a simple flat list containing all the elements across all levels.

For example, [[1,2],[3,4],[5,6]] would be flattened to [1,2,3,4,5,6]. All elements across all nested sublists are brought together into one linear list.

Flattening helps prepare nested list data for processing by algorithms that expect simple linear lists. It simplifies access and computation on list elements.

Solution

Here is how list flattening can be implemented:

Java

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
import java.util.*;

class Main {
  public static List<Integer> flatten(List<List<Integer>> nestedList) {
    List<Integer> flatList = new ArrayList<>();
    
    for (List<Integer> list : nestedList) {
      flatList.addAll(list);
    }
    return flatList;
  }
}

C++

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
#include <vector>
using namespace std;

vector<int> flatten(vector<vector<int>>& nestedVec) {
  vector<int> flatVec;
  
  for (auto list : nestedVec) {
    flatVec.insert(flatVec.end(), list.begin(), list.end()); 
  }

  return flatVec;
}

Python

1
2
3
4
5
6
7
8
def flatten(nested_list):
  
  flat_list = []
  
  for sublist in nested_list:
    flat_list.extend(sublist)

  return flat_list

The key steps are to iterate through each sublist and add/extend all elements into a new flat list.

Flattening helps simplify processing of nested lists or multidimensional data.

Description: List Flattening

List flattening refers to the process of converting a multi-level nested list into a single-level list, containing all the elements. The elements are usually arranged in the order they appear in the original nested list. This is often encountered in problems related to data transformation, parsing, and simplifying complex data structures.

Solution:

Below are examples to implement list flattening in Java, C++, and Python.

Java

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
import java.util.ArrayList;
import java.util.List;

public class ListFlattening {
    public static List<Integer> flatten(List<Object> nestedList) {
        List<Integer> flatList = new ArrayList<>();
        for (Object item : nestedList) {
            if (item instanceof Integer) {
                flatList.add((Integer) item);
            } else {
                flatList.addAll(flatten((List<Object>) item));
            }
        }
        return flatList;
    }

    public static void main(String[] args) {
        List<Object> nestedList = new ArrayList<>();
        nestedList.add(1);
        nestedList.add(Arrays.asList(2, Arrays.asList(3, 4), 5));
        nestedList.add(6);

        List<Integer> flatList = flatten(nestedList);
        System.out.println(flatList);
    }
}

C++

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <iostream>
#include <vector>
#include <variant>

std::vector<int> flatten(const std::vector<std::variant<int, std::vector<std::variant<int, std::vector<int>>>>>& nestedList) {
    std::vector<int> flatList;
    for (const auto& item : nestedList) {
        if (std::holds_alternative<int>(item)) {
            flatList.push_back(std::get<int>(item));
        } else {
            auto sublist = flatten(std::get<std::vector<std::variant<int, std::vector<int>>>>(item));
            flatList.insert(flatList.end(), sublist.begin(), sublist.end());
        }
    }
    return flatList;
}

int main() {
    std::vector<std::variant<int, std::vector<std::variant<int, std::vector<int>>>>> nestedList = {1, std::vector<std::variant<int, std::vector<int>>>{2, std::vector<int>{3, 4}, 5}, 6};
    auto flatList = flatten(nestedList);
    for (int num : flatList) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
}

Python

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
def flatten(nested_list):
    flat_list = []
    for item in nested_list:
        if isinstance(item, int):
            flat_list.append(item)
        else:
            flat_list.extend(flatten(item))
    return flat_list

if __name__ == "__main__":
    nested_list = [1, [2, [3, 4], 5], 6]
    flat_list = flatten(nested_list)
    print(flat_list)

Key Takeaways

Flattening can handle different levels of nesting.
It’s usually implemented using recursion to deal with multiple nested levels.
Java uses instanceof to check the type, C++ uses std::variant and std::holds_alternative, and Python uses isinstance.