Solve three classic coding problems

You are given three independent coding tasks. Implement a function for each. ## 1) Longest Increasing Subsequence (LIS) Given an integer array `nums`, return the length of the longest **strictly increasing** subsequence. - **Input:** `nums` (array of integers) - **Output:** integer length of the LIS - **Constraints (typical):** `1 <= n <= 2e5` (or smaller), values fit in 32-bit signed int ## 2) k-th Largest Element in Two Sorted Arrays Given two arrays `A` and `B`, each sorted in **non-decreasing** order, and an integer `k` (1-indexed), return the **k-th largest** element in the multiset union of `A` and `B`. - **Input:** `A`, `B` (sorted arrays), `k` - **Output:** the k-th largest element - **Notes:** Arrays may have different lengths; duplicates are allowed. - **Constraints (typical):** `0 <= len(A), len(B) <= 2e5`, `1 <= k <= len(A)+len(B)` ## 3) Connect Nodes at the Same Tree Level Given a **perfect** binary tree (all internal nodes have exactly two children and all leaves are at the same depth), populate each node’s `next` pointer so it points to its immediate neighbor to the right on the same level. If there is no neighbor, set `next = null`. - **Input:** root of a perfect binary tree with fields `left`, `right`, `next` - **Output:** the root (after pointers are populated) - **Requirement (typical):** use `O(1)` extra space (excluding recursion stack) ## 4) Number of Islands Given an `m x n` grid of characters containing `'1'` (land) and `'0'` (water), return the number of **connected components** of land. Cells are connected **4-directionally** (up/down/left/right). - **Input:** `grid` (2D array of `'0'`/`'1'`) - **Output:** integer number of islands - **Constraints (typical):** `1 <= m,n <= 200` (or similar)