[Java] Intuitive n^2 solution using BFS


  • 0
    R

    This solution is nowhere near as fast as DP + binary search but I think it's pretty intuitive and ran a bit faster than the naive n^2 DP solution that doesn't use binary search. The idea is to build a topologically sorted graph where nodes have an edge to other nodes whose value is larger and occur at higher index in the array. We then run BFS for each node and return the deepest level. The number of edges blows up so an optimization is to not add edges that result in a shorter path when we know about a longer path.

    For example, if we have [1, 2, 3] then we don't need to add an edge from 1 to 3 because we'll have a path from 1 to 3 through 2.

    public class Solution {
        private static class Graph {
            private int n;
            private List<List<Integer>> adjacent;
            
            public Graph(int n) {
                this.n = n;
                this.adjacent = new ArrayList<>(n);
                for (int i = 0; i < n; ++i) {
                    adjacent.add(i, new ArrayList<>());
                }
            }
            
            public void addEdge(int source, int target) {
                adjacent.get(source).add(target);
            }
            
            public List<Integer> adjacent(int source) {
                return adjacent.get(source);
            }
        }
        
        public int lengthOfLIS(int[] nums) {
            if (nums.length == 0 || nums.length == 1) {
                return nums.length;
            }
            
            Graph graph = buildGraph(nums);
            
            int maxSubsequence = 0;
            for (int i = 0; i < nums.length; ++i) {
                int subsequence = bfs(graph, i);
                if (subsequence > maxSubsequence) {
                    maxSubsequence = subsequence;
                }
                
                // Exit the loop since we cannot find longer than current max subsequence
                if (nums.length - i <= maxSubsequence) {
                    break;
                }
            }
            
            return maxSubsequence;
        }
        
        // Time: O(n^2), Space: O(n)
        private Graph buildGraph(int[] nums) {
            Graph graph = new Graph(nums.length);
            for (int j = nums.length - 1; j > 0; --j) {
                int maxNum = Integer.MIN_VALUE;
                for (int i = j - 1; i >= 0; --i) {
                    if (nums[i] < nums[j] && nums[i] > maxNum) {
                        graph.addEdge(i, j);
                        
                        if (nums[i] > maxNum) {
                            maxNum = nums[i];
                        }
                    }
                }
            }
            
            return graph;
        }
        
        // Time: O(|V| + |E|)
        private int bfs(Graph graph, int source) {
            Queue<Integer> queue = new ArrayDeque<>();
            queue.add(source);
            
            int maxDepth = 0;
            while (!queue.isEmpty()) {
                int queueSize = queue.size();
                for (int i = 0; i < queueSize; ++i) {
                    int head = queue.remove();
                    for (int tail : graph.adjacent(head)) {
                        queue.add(tail);
                    }
                }
                    
                ++maxDepth;
            }
            
            return maxDepth;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.