Java | easy to understand | monotonic stack | 3 subproblems | same as Leetcode 16737
1673. Find the Most Competitive Subsequence\n\n// TC-o(n)- Monotonously increasing stack\nclass Solution {\n    public int[] mostCompetitive(int[] nums, int k) 
# 1673. Find the Most Competitive Subsequence\n```\n// TC-o(n)- Monotonously increasing stack\nclass Solution {\n    public int[] mostCompetitive(int[] nums, int k) {\n        int n=nums.length;\n        Stack<Integer> st=new Stack<>();\n        int[] res=new int[k];\n        int rem=n-k;\n        for(int i=0;i<n;i++){\n            while(!st.isEmpty() && st.peek()>nums[i] && rem>0){\n                st.pop();\n                rem--;\n            }\n            st.push(nums[i]);\n            \n        }\n        while(rem>0){\n            st.pop();\n            rem--;\n        }\n        for(int i=k-1;i>=0;i--){\n            res[i]=st.pop();\n        }\n        return res;\n    }\n}\n```\n\n# 321. Create Maximum Number\n**3 Subproblems-**\n1. Find greatest numbers from nums1 and nums2 using the concept from leetcode 1673(monotonously decreasing stack here, that is the only change)\n2. Merge the two numbers(here they are in the form of arrays) such that it forms the greatest number\n3. Find the greatest among all the formed numbers.\nHere greatest means the number which is lexicographically greater.\n\n```\n// using the concept of 1673. Find the Most Competitive Subsequence\n// prob is we dn t know how many elements we will take from nums1 and nums2\n// so we will try for all combinations of k and find the max out of them\n\nclass Solution {\n    \n    // monotonic decreasing stack same as leetcode 1673 , only > changed to < \n\tpublic int[] findLexMax(int[] nums, int k) {\n\t\tint n = nums.length;\n\t\tStack<Integer> st = new Stack<>();\n\t\tint[] res = new int[k];\n        \n        /* we have to form a k digit number which is lexicographically greatest\n         that gives some hint that we need to maintain a monotonic decreasing stack\n         and rem=n-k means we will remove n-k smaller digits from stack\n         lets say nums=[6,7,4,8,9] and k=3, we have to remove 5-3=2 digits from the stack,\n         while we try to form monotonic decreasing satck\n         o our max number will be [8,9]\n         */\n\t\tint rem = n - k;\n\t\tfor (int i = 0; i < n; i++) {\n\t\t\twhile (!st.isEmpty() && st.peek() < nums[i] && rem > 0) {\n\t\t\t\tst.pop();\n\t\t\t\trem--;\n\t\t\t}\n\t\t\tst.push(nums[i]);\n\n\t\t}\n        \n        /* if still some elements can be removed, the best option would be to remove the\n        elements from the top of the stack, as we are mainting a monotonic decreasing satck\n        so elemets at the top would be smaller\n        take this example arr-[6,4,2] k=2 ans would be [6,4]\n        */\n\t\twhile (rem > 0) {\n\t\t\tst.pop();\n\t\t\trem--;\n\t\t}\n\t\tfor (int i = k - 1; i >= 0; i--) {\n\t\t\tres[i] = st.pop();\n\t\t}\n\t\treturn res;\n\t}\n    \n\n\tprivate static boolean findMax(int[] arr1, int[] arr2, int p1,int p2) {\n\t\twhile (p1 < arr1.length && p2 < arr2.length) {\n\t\t\tif (arr1[p1] < arr2[p2]) {\n\t\t\t\treturn false;\n\t\t\t} else if (arr1[p1] > arr2[p2]) {\n\t\t\t\treturn true;\n\t\t\t} else {\n\t\t\t\tp1++;\n\t\t\t\tp2++;\n\t\t\t}\n\t\t}\n        // when p1 is empty returns true, so that in merge function it picks up values of arr2\n        // when p1==arr1.length, then returns false,so that we keep pn picking arr2 elements\n\t\treturn p1!=arr1.length; // tricky\n\t}\n\n    \n\t// think of the case [6,0,4] and [6,7], can t do simple logic like merge two sorted arrays\n    // we need to decide which pointer to move forward based on the rest of the array,\n    // if both elements are same compare the next element, and then decide\n\tprivate int[] merge(int[] nums1, int[] nums2, int k) {\n\t\tint[] res = new int[k];\n\t\tint resIndex = 0;\n\t\tint p1 = 0;\n\t\tint p2 = 0;\n        \n\t\twhile (resIndex<res.length) {\n\t\t\tres[resIndex++]=findMax(nums1,nums2,p1,p2)?nums1[p1++]:nums2[p2++];// tricky\n\t\t}\n\n\t\treturn res;\n\t}\n\n\tpublic int[] maxNumber(int[] nums1, int[] nums2, int k) {\n\t\tint len1 = nums1.length;\n\t\tint len2 = nums2.length;\n\t\tint[] maxRes = new int[k];\n\t\tfor (int i = 0; i <= k; i++) { \n\t\t\tint j = k - i;\n\t\t\tif (i <= len1 && (k - i) <= len2) { // skip invalid cases, imp step!\n\t\t\t\tint[] maxLex1 = findLexMax(nums1, i);\n\t\t\t\tint[] maxLex2 = findLexMax(nums2, j);\n\t\t\t\tint[] res = merge(maxLex1, maxLex2, k);\n\t\t\t\tboolean compareRes = findMax(res, maxRes,0,0);\n\t\t\t\tif (compareRes) {\n\t\t\t\t\tmaxRes = res;\n\t\t\t\t}\n\t\t\t}\n\t\t}\n\t\treturn maxRes;\n\t}\n    \n}\n```
['Monotonic Stack', 'Java']