#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

vector<int> coinPairIndices(vector<int>& coins, int target) {
    unordered_map<int, int> mp;
    for (int i = 0; i < coins.size(); i++) {
        int complement = target - coins[i];
        if (mp.count(complement))
            return { mp[complement], i };
        mp[coins[i]] = i;
    }
    return { -1, -1 };
}

int main() {
    vector<int> coins = {2, 7, 11, 15};
    auto res = coinPairIndices(coins, 9);
    cout << "[" << res[0] << ", " << res[1] << "]" << endl; // [0, 1]
}

def coin_pair_indices(coins, target):
    seen = {}
    for i, val in enumerate(coins):
        complement = target - val
        if complement in seen:
            return [seen[complement], i]
        seen[val] = i
    return [-1, -1]

# Test
coins = [2, 7, 11, 15]
print(coin_pair_indices(coins, 9))  # [0, 1]

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> mergeSorted(vector<int> A, vector<int> B) {
    reverse(B.begin(), B.end());
    vector<int> result;
    int i = 0, j = 0;
    while (i < A.size() && j < B.size())
        result.push_back(A[i] <= B[j] ? A[i++] : B[j++]);
    while (i < A.size()) result.push_back(A[i++]);
    while (j < B.size()) result.push_back(B[j++]);
    return result;
}

int main() {
    vector<int> A = {1,3,5,7}, B = {10,8,6,4};
    for (auto v : mergeSorted(A, B)) cout << v << " ";
    // 1 3 4 5 6 7 8 10
}

def merge_sorted(A, B):
    B_asc = B[::-1]   # reverse B to ascending
    result = []
    i = j = 0
    while i < len(A) and j < len(B_asc):
        if A[i] <= B_asc[j]:
            result.append(A[i]); i += 1
        else:
            result.append(B_asc[j]); j += 1
    result.extend(A[i:])
    result.extend(B_asc[j:])
    return result

print(merge_sorted([1,3,5,7], [10,8,6,4]))
# [1, 3, 4, 5, 6, 7, 8, 10]

#include <iostream>
#include <vector>
using namespace std;

int firstOccurrence(vector<int>& arr, int target) {
    for (int i = 0; i < arr.size(); i++)
        if (arr[i] == target) return i;
    return -1;
}

int main() {
    vector<int> arr = {4,2,7,2,9,2};
    cout << firstOccurrence(arr, 2) << endl; // 1
    cout << firstOccurrence(arr, 3) << endl; // -1
}

def first_occurrence(arr, target):
    for i, val in enumerate(arr):
        if val == target:
            return i
    return -1

print(first_occurrence([4,2,7,2,9,2], 2))  # 1
print(first_occurrence([5,8,1,6], 3))          # -1

#include <iostream>
#include <queue>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int v) : val(v), left(nullptr), right(nullptr) {}
};

int minDepth(TreeNode* root) {
    if (!root) return 0;
    queue<TreeNode*> q;
    q.push(root);
    int depth = 1;
    while (!q.empty()) {
        int sz = q.size();
        for (int i = 0; i < sz; i++) {
            auto node = q.front(); q.pop();
            if (!node->left && !node->right) return depth;
            if (node->left)  q.push(node->left);
            if (node->right) q.push(node->right);
        }
        depth++;
    }
    return depth;
}

int main() {
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    cout << minDepth(root) << endl; // 2
}

from collections import deque

class TreeNode:
    def __init__(self, val=0):
        self.val = val
        self.left = self.right = None

def min_depth(root):
    if not root: return 0
    q = deque([(root, 1)])
    while q:
        node, depth = q.popleft()
        if not node.left and not node.right:
            return depth   # leaf!
        if node.left:  q.append((node.left,  depth + 1))
        if node.right: q.append((node.right, depth + 1))

# Build: 1 → (2→4, 3)
root = TreeNode(1)
root.left, root.right = TreeNode(2), TreeNode(3)
root.left.left = TreeNode(4)
print(min_depth(root))  # 2