Problem Set Overview

• 3105. Longest Strictly Increasing or Decreasing Subarray
• 3106. Lexicographically Smallest String with Distance Constraint
• 3107. Minimum Operations to Make Median Equal to K
• 3108. Minimum Cost Path in Weighted Graph

Longest Strictly Monotonic Subarray

The solution involves simulating the problem requirements. Two approaches are presented: Approach 1: Two-pass traversal - separately handle increasing and decreasing sequences using grouped loops. Approach 2: Single-pass traversal. Consider the moontonic property by treating points as connected lines forming a polyline (or function). Since increasing and decreasing sequences don't affect each other independently, we can track both upward and downward polyline lengths in one iteration. ``` // Two passes: calculate increasing and decreasing separately class Solution { public: int longestMonotonicSubarray(vector& values) { int result = 1, size = values.size();

    // Check increasing sequences
    for(int start = 0; start < size;) {
        int initial = start++;
        while(start < size && values[start] > values[start-1])
            start++;
        result = max(start - initial, result);
    }
    
    // Check decreasing sequences
    for(int start = 0; start < size;) {
        int initial = start++;
        while(start < size && values[start] < values[start-1])
            start++;
        result = max(start - initial, result);
    }
    return result;
}

};

// Single pass: calculate both increasing and decreasing simultaneously class Solution { public: int longestMonotonicSubarray(vector& values) { int result = 1, size = values.size();

    for(int index = 1; index < size;) {
        if(values[index] == values[index-1]) {
            index++;
            continue;
        }
        
        // false means values[index-1] > values[index] (decreasing)
        // true means values[index-1] < values[index] (increasing)
        bool isIncreasing = values[index-1] < values[index];
        int start = index++;
        
        while(index < size && values[index] != values[index-1] && 
              (values[index-1] < values[index]) == isIncreasing) {
            index++;
        }
        result = max(index - start + 1, result);
    }
    return result;
}

};

</div>Lexicographically Smallest String with Distance Constraint
----------------------------------------------------------

This problem uses simple greedy strategy: prioritize transforming leftmost characters toward 'a' to achieve minimal lexicographical order. Since the alphabet transformation is circular (26 letters), consider whether direct transformation to 'a' requires fewer operations than going backward through 'z' to 'a'. <div class="code-block">```
class Solution {
public:
    string getSmallestString(string input, int operations) {
        for(auto& character : input) {
            int forwardSteps = character - 'a';      // Steps to reach 'a' directly
            int backwardSteps = 'z' - character + 1; // Steps via 'z' to 'a'
            int minSteps = min(forwardSteps, backwardSteps);
            
            if(minSteps <= operations) {
                character = 'a';
                operations -= minSteps;
            } else {
                character -= operations; // Move as close to 'a' as possible
                break;
            }
        }
        return input;
    }
};

The goal is to change the median through +1/-1 operations with minimum steps. Using greedy approach, consider how many numbers remain unmodified - those that don't affect the target median. When index <= middle && array[index] <= target OR index >= middle && array[index] > target (where middle represents median index), no operations are needed. ``` class Solution { public: long long minOperationsToMakeMedianK(vector& numbers, int target) { int length = numbers.size(); sort(numbers.begin(), numbers.end());

    long long operations = 0;
    int medianIndex = length / 2; // For odd: middle, for even: right middle
    
    if(numbers[medianIndex] < target) {
        for(int idx = medianIndex; idx < length; idx++) {
            if(numbers[idx] >= target)
                break;
            operations += target - numbers[idx];
        }
    } else if(numbers[medianIndex] > target) {
        for(int idx = medianIndex; idx >= 0; idx--) {
            if(numbers[idx] <= target)
                break;
            operations += numbers[idx] - target;
        }
    }
    return operations;
}

};

</div>For more complex scenarios where multiple targets (k1, k2, k3...) need processing, the time complexity becomes O(n\*m) using the basic approach. This can be optimized using prefix sums for preprocessing and binary search to locate interval boundaries in O(1) time, achieving O(m\*log n) complexity. Minimum Cost Path in Weighted Graph
-----------------------------------

Key ensights: 1. **AND operation properties**: More numbers participating in AND operations yield smaller results 2. **Revisiting edges/nodes** is allowed Since AND operations are involved, traversing all paths in the connected component containing both nodes will yield minimum cost. Two scenarios exist: - Connected nodes: Result equals AND of all edge weights in their connected component - Disconnected nodes: Return -1 Special case: Same source and destination returns 0. Union-Find data structure handles connectivity partitioning effectively. <div class="code-block">```
class Solution {
public:
    vector<int> minimumCost(int nodeCount, vector<vector<int>>& edges, vector<vector<int>>& queries) {
        // cost initialized to -1 since -1 has all bits set, won't affect AND operations
        vector<int> parent(nodeCount, -1), cost(nodeCount, -1);
        
        function<int(int)> findParent = [&](int x) -> int {
            return parent[x] == -1 ? x : parent[x] = findParent(parent[x]);
        };
        
        for(auto& edge : edges) {
            int u = edge[0], v = edge[1], weight = edge[2];
            int rootU = findParent(u), rootV = findParent(v);
            
            if(rootU != rootV) {
                parent[rootU] = rootV; // Merge sets, using rootV as final parent
                cost[rootV] &= cost[rootU]; // Calculate cost considering parent relationship
            }
            cost[rootV] &= weight;
        }
        
        int queryCount = queries.size();
        vector<int> result(queryCount);
        
        for(int i = 0; i < queryCount; i++) {
            int src = queries[i][0], dst = queries[i][1];
            int srcRoot = findParent(src), dstRoot = findParent(dst);
            
            if(srcRoot != dstRoot) 
                result[i] = -1;
            else 
                result[i] = (src == dst) ? 0 : cost[srcRoot];
        }
        return result;
    }
};

    vector<int> componentId(nodeCount, -1);
    vector<int> costs;
    
    function<int(int)> dfs = [&](int node) -> int {
        componentId[node] = costs.size();
        int value = -1;
        
        for(auto [neighbor, weight] : graph[node]) {
            value &= weight;
            if(componentId[neighbor] < 0) {
                value &= dfs(neighbor);
            }
        }
        return value;
    };

    for(int i = 0; i < nodeCount; i++) {
        if(componentId[i] == -1) {
            costs.push_back(dfs(i));
        }
    }

    int queryCount = queries.size();
    vector<int> result(queryCount);
    
    for(int i = 0; i < queryCount; i++) {
        int src = queries[i][0], dst = queries[i][1];
        int srcComponent = componentId[src], dstComponent = componentId[dst];
        
        if(srcComponent != dstComponent) 
            result[i] = -1;
        else 
            result[i] = costs[srcComponent];
    }
    return result;
}

};

</div>