i want to remove the duplicate sub integer arraylist from an integer arraylist in java

Question

you are given an nested array list such as : list = [[-1,2,1],[-2,-2,4],[-1,2,-1],[-1,-2,3],[-1,2,-1]]

i want to have an output like this : [[-1,2,1],[-2,-2,4],[-1,-2,3]]

but its not likely to come with the code i am using...

for(int i=0;i<list.size();i++){
for(int j=i+1;j<list.size();j++){
if(list.get(i).eqauls(list.get(j)))
 {
 list.remove(list.get(j));
  }
  }
  }
 System.out.println(list);

i have done like this but its not taking and duplicates are still there so i have done in another way something like this...

List<List<Integer>> list2=  new ArrayList<List<Integer>>();
for(int i=0;i<list.size();i++){
for(int j=i+1;j<list.size();j++){
if(!list.get(i).eqauls(list.get(j)))
 {
 List<Integer> p= new ArrayList<Integer>();
 for(int m=0;m<list.size();m++){
 for(int n=0;n<list.get(i).size();n++){
 p.add(list.get(i).get(m));
 list2.add(p);
 }
 }
 }
System.out.println(list2);

Output: Run time error What should i do in this case....only using array list data structures only...

Answer 1

Strategy

We can build a tree data structure, the paths of which are exactly the unique sub-lists contained within your master list. Once the tree is built, we can iterate over it, e.g. with a recursive algorithm, and re-build a master list of lists, without any duplicates.

Code

import java.util.*;

public class ListUnduper{

     public static void main(String []args){
        Tree root = new Tree();
        List<List<Integer>> list = new ArrayList<>();
        List<Integer> first = new ArrayList<Integer>(); 
        first.add(1); first.add(2);
        List<Integer> second = new ArrayList<Integer>(); 
        //Add more lists here if you like
        list.add(first); list.add(second);
        for(int i=0;i<list.size();i++){
          List<Integer> inner = list.get(i);
          Tree current = root;
          for(int j=i+1;j<inner.size();j++){
            int nextElement = inner.get(j);        
            if(!current.children.containsKey(nextElement)){
              current.children.put(nextElement, new Tree());
            }
            current = current.children.get(nextElement);
           }
        }

        List<List<Integer>> master = new ArrayList<List<Integer>>();
        List<Integer> emptyPrefix = new ArrayList<Integer>();
        addAllToList(emptyPrefix, master, root);    

        //master now should contain all non-dupes 
     }

    static void addAllToList(List<Integer> prefix, List<List<Integer>> master, Tree tree){
      for(Map.Entry<Integer,Tree> entry : tree.children.entrySet()){
        Tree nextTree = entry.getValue();  
        //I believe this makes a deep copy
        List<Integer> nextPrefix = new ArrayList<>(prefix);
        nextPrefix.add(entry.getKey());
        if(nextTree.children.isEmpty()){
          master.add(nextPrefix);
        }
        else{
          addAllToList(nextPrefix, master, tree);
        }
      }
    }
}

class Tree{
  HashMap<Integer, Tree> children = new HashMap<Integer, Tree>();
}

Warning: using recursion may result in Stackoverflow errors if your lists are large. In that case, it's advisable to switch to using a while loop, but the algorithm will likely be more complicated to code in that case.

Note on Order of Elements

As this alternative answer points out, the original order of lists within the master list may be important. The above solution does not guarantee preserving such an order.