How to find subsequent elements in a List with none-null property and update previous elements based-CodePudding

I have stuck on at-first-sight simple problem.

Let's assume we have a simple Person class:

class Person {
    String name;
    String company;
}

And the input:

List<Person> persons = List.of(
            new Person("Bill", null),
            new Person("Andrew", null),
            new Person("Chris", "Magic"),
            new Person("Max", null),
            new Person("Garry", null),
            new Person("Mark", "Risky")
    );

I need the following result with the strict condition: escape "O(n)" complexity, so sorting and reverse are unacceptable. What's the most efficient way to fill this company String value from subsequent elements over one iteration?

 List<Person> resultPersons = List.of(
            new Person("Bill", "Magic"),
            new Person("Andrew", "Magic"),
            new Person("Chris", "Magic"),
            new Person("Max", "Risky"),
            new Person("Garry", "Risky"),
            new Person("Mark", "Risky")
    );

Input data can be in the millions of more complex objects, and the best possible efficiency matters.

My current approach:

// key - person id, value - company
NavigableMap<Integer, String> companyDict = new TreeMap<>();

List<PersonCard> result = persons.stream()
      .sorted(PERSON_COMPARATOR)
      .peek(p -> fillCompanyName(p, companyDict)) // fill map with personId and company
      .map(p -> createPersonCard(p, companyDict)) // use map with companies to get company by person id for creating another object
      .collect(Collectors.toList());

 Collections.reverse(result);

And it is not acceptable.

CodePudding user response：

The simplest approach which runs in O(n) would be to maintain a List objects that need to be updated and while iterating over the given list.

And for each element, check if its company property is equal to null. If that's the case, the elements should be added to the list of Person instance that should be updated. Otherwise, if the list is not empty, all its elements should be assigned with the property of the next element and than the list needs to be cleaned out.

That's how implementation might look like:

List<Person> persons = List.of(
    new Person("Bill", null),
    new Person("Andrew", null),
    new Person("Chris", "Magic"),
    new Person("Max", null),
    new Person("Garry", null),
    new Person("Mark", "Risky")
);
        
List<Person> toUpdate = new ArrayList<>();
for (Person person : persons) {
    if (person.getCompany() == null) toUpdate.add(person);
    else if (!toUpdate.isEmpty()) {
        toUpdate.forEach(p -> p.setCompany(person.getCompany()));
        toUpdate = new ArrayList<>();
    }
}
        
persons.forEach(System.out::println);

Output:

Person1{name='Bill', company='Magic'}
Person1{name='Andrew', company='Magic'}
Person1{name='Chris', company='Magic'}
Person1{name='Max', company='Risky'}
Person1{name='Garry', company='Risky'}
Person1{name='Mark', company='Risky'}

Note

In order to solve the problem by performing as fewer actions as possible and minimizing allocated space we need to maintain a state during the iteration. And designing stateful stream pipelines (like the one in your code), which accumulate the state outside the stream in not encouraged by the Stream API doucmentation.

This logic can be implemented using streams (without modifying the objects outside the stream) but such solution would be way more harder to digest than a plain for-loop presented above.