Abstract
Given a sequence of integers, we want to find a longest increasing subsequence of the sequence. It is known that this problem can be solved in \(O\left (n \log n\right )\) time and space. Our goal in this paper is to reduce the space consumption while keeping the time complexity small. For \(\sqrt {n} \le s \le n\), we present algorithms that use \(O\left (s \log n\right )\) bits and \(O\left (\frac {1}{s} \cdot n^{2} \cdot \log n\right )\) time for computing the length of a longest increasing subsequence, and \(O\left (\frac {1}{s} \cdot n^{2} \cdot \log ^{2} n\right )\) time for finding an actual subsequence. We also show that the time complexity of our algorithms is optimal up to polylogarithmic factors in the framework of sequential access algorithms with the prescribed amount of space.
Similar content being viewed by others
Notes
This algorithm outputs a longest increasing subsequence in the reversed order. One can access the input in the reversed order and find a longest decreasing subsequence to avoid this issue.
Again this output is reversed. We can also compute the output in nonreversed order as discussed before.
References
Ahn, H.-K., Baraldo, N., Oh, E., Silvestri, F.: A time-space trade-off for triangulations of points in the plane. In: COCOON 2017, pp 3–12 (2017). https://doi.org/10.1007/978-3-319-62389-4_1
Aldous, D., Diaconis, P.: Longest increasing subsequences: from patience sorting to the Baik-Deift-Johansson theorem. Bull. Am. Math. Soc. 36 (4), 413–432 (1999). https://doi.org/10.1090/S0273-0979-99-00796-X
Asano, T., Elmasry, A., Katajainen, J.: Priority queues and sorting for read-only data. In: TAMC 2013, pp 32–41 (2013). https://doi.org/10.1007/978-3-642-38236-9_4
Asano, T., Izumi, T., Kiyomi, M., Konagaya, M., Ono, H., Otachi, Y., Schweitzer, P., Tarui, J., Uehara, R.: Depth-first search using O(n) bits. In: ISAAC 2014, pp 553–564 (2014). https://doi.org/10.1007/978-3-319-13075-0_44
Banyassady, B., Korman, M., Mulzer, W., Van Renssen, André, Roeloffzen, M., Seiferth, P., Stein, Y.: Improved time-space trade-offs for computing Voronoi diagrams. In: STACS 2017, vol. 66, pp 9:1–9:14 (2017). https://doi.org/10.4230/LIPIcs.STACS.2017.9
Bespamyatnikh, S., Segal, M.: Enumerating longest increasing subsequences and patience sorting. Inf. Process. Lett. 76(1–2), 7–11 (2000). https://doi.org/10.1016/S0020-0190(00)00124-1
Borodin, A., Cook, S.: A time-space tradeoff for sorting on a general sequential model of computation. SIAM J. Comput. 11(2), 287–297 (1982). https://doi.org/10.1137/0211022
Burstein, A., Lankham, I.: Combinatorics of patience sorting piles. Séminaire Lotharingien de Combinatoire 54A, B54Ab (2006). http://www.mat.univie.ac.at/~slc/wpapers/s54Aburlank.html
Chakraborty, S., Satti, S.R.: Space-efficient algorithms for maximum cardinality search, stack BFS, queue BFS and applications. In: COCOON 2017, pp 87–98 (2017). https://doi.org/10.1007/978-3-319-62389-4_8
Chan, T.M., Chen, E.Y.: Multi-pass geometric algorithms. Discret. Comput. Geom. 37(1), 79–102 (2007). https://doi.org/10.1007/s00454-006-1275-6
Cook, S.A.: Deterministic CFL’s are accepted simultaneously in polynomial time and log squared space. In: STOC 1979, pp 338–345 (1979), https://doi.org/10.1145/800135.804426
Crochemore, M., Porat, E.: Fast computation of a longest increasing subsequence and application. Inf. Comput. 208(9), 1054–1059 (2010). https://doi.org/10.1016/j.ic.2010.04.003
Darwish, O., Elmasry, A.: Optimal time-space tradeoff for the 2D convex-hull problem. In: ESA 2014, pp 284–295 (2014). https://doi.org/10.1007/978-3-662-44777-2_24
Elmasry, A., Hagerup, T., Kammer, F.: Space-efficient basic graph algorithms. In: STACS 2015, vol. 30, pp 288–301 (2015). https://doi.org/10.4230/LIPIcs.STACS.2015.288
Ergun, F., Jowhari, H.: On the monotonicity of a data stream. Combinatorica 35(6), 641–653 (2015). https://doi.org/10.1007/s00493-014-3035-1
Frederickson, G.N.: Upper bounds for time-space trade-offs in sorting and selection. J Comput Syst Sci 34(1), 19–26 (1987). https://doi.org/10.1016/0022-0000(87)90002-X
Fredman, M.L.: On computing the length of longest increasing subsequences. Discret. Math. 11(1), 29–35 (1975). https://doi.org/10.1016/0012-365X(75)90103-X
Gál, A., Gopalan, P.: Lower bounds on streaming algorithms for approximating the length of the longest increasing subsequence. SIAM J. Comput. 39(8), 3463–3479 (2010). https://doi.org/10.1137/090770801
Gopalan, P., Jayram, T.S., Krauthgamer, R., Kumar, R.: Estimating the sortedness of a data stream. In: SODA 2007, pp 318–327 (2007). http://dl.acm.org/citation.cfm?id=1283417
Hunt, J.W., Szymanski, T.G.: A fast algorithm for computing longest common subsequences. Commun. ACM 20(5), 350–353 (1977). https://doi.org/10.1145/359581.359603
Kushilevitz, E., Nisan, N.: Communication complexity. Cambridge University Press, Cambridge (1997)
Liben-Nowell, D., Vee, E., An, Z.: Finding longest increasing and common subsequences in streaming data. J. Comb. Optim. 11(2), 155–175 (2006). https://doi.org/10.1007/s10878-006-7125-x
Lincoln, A., Williams, V.V., Wang, J.R., Ryan Williams, R.: Deterministic time-space trade-offs for k-SUM. In: ICALP 2016, pp 58:1–58:14 (2016), https://doi.org/10.4230/LIPIcs.ICALP.2016.58
Mallows, C.L.: Problem 62-2, patience sorting. SIAM Rev. 4(2), 143–149 (1962). http://www.jstor.org/stable/2028371
Mallows, C.L.: Problem 62-2. SIAM Rev. 5(4), 375–376 (1963). http://www.jstor.org/stable/2028347
Mallows, C.L.: Patience sorting. Bulletin of the Institute of Mathematics and its Applications 9, 216–224 (1973)
Munro, J.I., Paterson, M.S.: Selection and sorting with limited storage. Theor. Comput. Sci. 12(3), 315–323 (1980). https://doi.org/10.1016/0304-3975(80)90061-4
Naumovitz, T., Saks, M.: A polylogarithmic space deterministic streaming algorithm for approximating distance to monotonicity. In: SODA 2015, pp 1252–1262 (2015). https://doi.org/10.1137/1.9781611973730.83
Nisan, N.: RL \(\subseteq \) SC. In: STOC 1992, pp 619–623 (1992). https://doi.org/10.1145/129712.129772
Pagter, J., Rauhe, T.: Optimal time-space trade-offs for sorting. In: FOCS 1998, pp 264–268 (1998). https://doi.org/10.1109/SFCS.1998.743455
Pilipczuk, M., Wrochna, M.: On space efficiency of algorithms working on structural decompositions of graphs. In: STACS 2016, vol. 47, pp 57:1–57:15 (2016). https://doi.org/10.4230/LIPIcs.STACS.2016.57
Ramanan, P.: Tight \(\Omega (n \lg n)\) lower bound for finding a longest increasing subsequence. Int. J. Comput. Math. 65(3–4), 161–164 (1997). https://doi.org/10.1080/00207169708804607
Romik, D.: The surprising mathematics of longest increasing subsequences. Cambridge University Press, Cambridge (2015). https://doi.org/10.1017/CBO9781139872003
Saks, M., Seshadhri, C.: Space efficient streaming algorithms for the distance to monotonicity and asymmetric edit distance. In: SODA 2013, pp 1698–1709 (2013). https://doi.org/10.1137/1.9781611973105.122
Saks, M., Seshadhri, C: Estimating the longest increasing sequence in polylogarithmic time. SIAM J. Comput. 46(2), 774–823 (2017). https://doi.org/10.1137/130942152
Savitch, W.J.: Relationships between nondeterministic and deterministic tape complexities. J. Comput. Syst. Sci. 4(2), 177–192 (1970). https://doi.org/10.1016/S0022-0000(70)80006-X
Schensted, C.: Longest increasing and decreasing subsequences. Can. J. Math. 13(2), 179–191 (1961). https://doi.org/10.4153/CJM-1961-015-3
Su, X., Woodruff, D.P.: The communication and streaming complexity of computing the longest common and increasing subsequences. In: SODA 2007, pp 336–345 (2007). http://dl.acm.org/citation.cfm?id=1283383.1283419
Wang, J.R.: Space-efficient randomized algorithms for K-SUM. In: ESA 2014, pp 810–829 (2014). https://doi.org/10.1007/978-3-662-44777-2_67
Acknowledgments
The authors are grateful to William S. Evans for bringing the reduction from LCS to LIS mentioned in the concluding remarks to their attention.
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher’s Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
This article is part of the Topical Collection on Special Issue on Theoretical Aspects of Computer Science (2018)
Partially supported by MEXT/JSPS KAKENHI grant numbers JP17H01698, JP18H04091, JP18K11168, JP18K11169, JP24106004. A preliminary version appeared in the proceedings of the 35th International Symposium on Theoretical Aspects of Computer Science (STACS 2018), vol. 96 of Leibniz International Proceedings in Informatics, pp. 44:1-44:15, 2018.
Rights and permissions
About this article
Cite this article
Kiyomi, M., Ono, H., Otachi, Y. et al. Space-Efficient Algorithms for Longest Increasing Subsequence. Theory Comput Syst 64, 522–541 (2020). https://doi.org/10.1007/s00224-018-09908-6
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00224-018-09908-6