number of subarrays with exactly K different integers.

Given:

 An array A[] of positive integers.

 An integer K.

Task:
Return the number of subarrays of A that contain exactly K distinct integers.

A = [1,2,1,2,3], K = 2

import java.util.*;

class Solution {

public int subarraysWithKDistinct(int[] A, int K) {

return atMostK(A, K) - atMostK(A, K - 1);

private int atMostK(int[] A, int K) {

int i = 0, count = 0;

Map<Integer, Integer> freq = new HashMap<>();

for (int j = 0; j < A.length; j++) {

if (freq.getOrDefault(A[j], 0) == 0) K--;

freq.put(A[j], freq.getOrDefault(A[j], 0) + 1);

while (K < 0) {

freq.put(A[i], freq.get(A[i]) - 1);

if (freq.get(A[i]) == 0) K++;

i++;

count += j - i + 1;

}
 return count;

public static void main(String[] args) {

Scanner sc = new Scanner(System.in);

int n = sc.nextInt(); // length of array

int k = sc.nextInt(); // target K

int[] arr = new int[n];

for (int i = 0; i < n; i++) arr[i] = sc.nextInt();

Solution sol = new Solution();

System.out.println(sol.subarraysWithKDistinct(arr, k));

Write a JAVA Program to find shortest sub array with sum at least K

Return the length of the shortest, non-empty, contiguous subarray of A with sum at least K. If there is
no non-empty subarray with sum at least K, return -1.

Example 1: Input: A = [1], K = 1

Output: 1

import java.util.*;

public class ShortestSubarray {

public int shortestSubarray(int[] A, int K) {

int N = A.length;

long[] prefixSum = new long[N + 1];

// Step 1: Compute prefix sums

for (int i = 0; i < N; i++) {

prefixSum[i + 1] = prefixSum[i] + (long) A[i];

}
 int result = N + 1; // Initialize with impossible length

Deque<Integer> deque = new LinkedList<>();

// Step 2: Sliding window over prefix sums

for (int y = 0; y <= N; y++) {

// Maintain deque increasing: Remove indices with larger prefixSum

while (!deque.isEmpty() && prefixSum[y] <= prefixSum[deque.getLast()]) {

deque.removeLast();

// Check if the current prefixSum[y] can form a valid subarray

while (!deque.isEmpty() && prefixSum[y] - prefixSum[deque.getFirst()] >= K) {

result = Math.min(result, y - deque.removeFirst());

// Add current index

deque.addLast(y);

return result <= N ? result : -1;

public static void main(String[] args) {

Scanner sc = new Scanner(System.in);

int n = sc.nextInt(); // Array length

int k = sc.nextInt(); // Target sum K

int[] arr = new int[n];

for (int i = 0; i < n; i++) {

arr[i] = sc.nextInt();
 }

ShortestSubarray obj = new ShortestSubarray();

System.out.println(obj.shortestSubarray(arr, k));

Write a JAVA Program to implement Fenwick Tree

Malika taught a new fun time program practice for Engineering Students.

As a part of this she has given set of numbers, and asked the students to find the gross value of
numbers between indices S1 and S2 (S1<=S2), inclusive.

Now it’s your task to create a method sumRange(S1,S2) which return the sum of numbers between
the indices S1 and S2, both are inclusive.

Input Format:

Line-1: An integer n, size of the array(set of numbers).

Line-2: n space separated integers.

Line-3: Two integers s1 and s2, index positions where s1<=s2.

Output Format: An integer, sum of integers between indices(s1, s2).

Sample Input-1: 8 1 2 13 4 25 16 17 8 2 6

Sample Output-1: 75

Constraints: 1 <= nums.length <= 3 * 104

-100 <= nums[i] <= 100 0 <= index < nums.length -100 <= val <= 100

0 <= left <= right < nums.length

At most 3 * 104 calls will be made to update and sumRange.

import java.util.*;

class FenWickTree

int[] nums;

int[] BIT;

int n;

public FenWickTree(int[] nums)

this.nums = nums;
n = nums.length;

BIT = new int[n + 1];

for (int i = 0; i < n; i++)

init(i, nums[i]);

public void init(int i, int val) {

i++;

while (i <= n) {

BIT[i] += val;

i += (i & -i);

void update(int i, int val) {

int diff = val - nums[i];

nums[i] = val;

init(i, diff);

public int getSum(int i)

int sum = 0;

i++;

while (i > 0)

sum += BIT[i];

i -= (i & -i);

}
return sum;

public int sumRange(int i, int j)

return getSum(j) - getSum(i - 1);

public static void main(String args[] )

Scanner scan = new Scanner(System.in);

int n=scan.nextInt();

int q=scan.nextInt();

int[] nums=new int[n];

for(int i=0; i<n; i++)

nums[i] = scan.nextInt();

FenWickTree ft =new FenWickTree(nums);

while(q-->0)

int opt=scan.nextInt();

if(opt==1)

int s1 = scan.nextInt();

int s2 = scan.nextInt();

System.out.println(ft.sumRange(s1,s2));

else

int ind = scan.nextInt();

ft.update(ind,val);

Sample input :

-8 5

1 2 13 4 25 16 17 8

126

107

2 2 18

2 4 17

127

Out put : 75 86 80

Write a JAVA Program to implement a segment tree with its operations In Hyderabad after a long
pandemic gap, the Telangana Youth festival Is Organized at HITEX.

In HITEX, there are a lot of programs planned. During the festival in order to maintain the rules of
Pandemic, they put a constraint that one person can only attend any one of the programs in one day
according to planned days.

Now it’s your aim to implement the "Solution" class in such a way that you need to return the
maximum number of programs you can attend according to given constraints. Explanation: You have
a list of programs ‘p’ and days ’d’, where you can attend only one program on one day.

Programs [p] = [first day, last day], p is the program's first day and the last day.

Input Format: Line-1: An integer N, number of programs. Line-2: N comma separated pairs, each
pair(f_day, l_day) is separated by space.

Output Format: An integer, the maximum number of programs you can attend. Sample

Input-1: 4 1 2,2 4,2 3,2 2

Sample Output-1: 4

Sample Input-2: 6 1 5,2 3,2 4,2 2,3 4,3 5

Sample Output-2:

5
import java.util.*;

class Solution {

class SegmentTreeNode {

int start, end;

SegmentTreeNode left, right;

int val;

public SegmentTreeNode(int start, int end) {

this.start = start;

this.end = end;

left = null;

right = null;

val = start;

SegmentTreeNode root;

public int maxEvents(int[][] events) {

if (events == null || events.length == 0)

return 0;

// Sort by end day (greedy)

Arrays.sort(events, (a, b) -> {

if (a[1] == b[1])

return a[0] - b[0];

return a[1] - b[1];

});

int lastDay = 0;
 int firstDay = Integer.MAX_VALUE;

for (int[] e : events) {

firstDay = Math.min(firstDay, e[0]);

lastDay = Math.max(lastDay, e[1]);

root = buildSegmentTree(firstDay, lastDay);

int count = 0;

for (int[] event : events) {

int earliestDay = query(root, event[0], event[1]);

if (earliestDay != Integer.MAX_VALUE) {

count++;

update(root, earliestDay);

return count;

private SegmentTreeNode buildSegmentTree(int start, int end) {

if (start > end)

return null;

SegmentTreeNode node = new SegmentTreeNode(start, end);

if (start != end) {

int mid = start + (end - start) / 2;

node.left = buildSegmentTree(start, mid);

node.right = buildSegmentTree(mid + 1, end);

return node;
 }

private void update(SegmentTreeNode curr, int day) {

if (curr.start == curr.end) {

curr.val = Integer.MAX_VALUE;

return;

int mid = curr.start + (curr.end - curr.start) / 2;

if (day <= mid) {

update(curr.left, day);

} else {

update(curr.right, day);

curr.val = Math.min(curr.left.val, curr.right.val);

private int query(SegmentTreeNode curr, int left, int right) {

if (curr.start > right || curr.end < left)

return Integer.MAX_VALUE;

if (curr.start >= left && curr.end <= right)

return curr.val;

return Math.min(query(curr.left, left, right), query(curr.right, left, right));

public class MaxEvents {

public static void main(String[] args) {

int n = scan.nextInt();

scan.nextLine();

String[] str = scan.nextLine().split(",");

int[][] nums = new int[n][2];

for (int i = 0; i < n; i++) {

String[] val = str[i].trim().split(" ");

nums[i][0] = Integer.parseInt(val[0]);

nums[i][1] = Integer.parseInt(val[1]);

Solution sol = new Solution();

int result = sol.maxEvents(nums);

System.out.println(result);

) Write a JAVA Program to implement TREAP with its operations

Given an integer array nums, return the number of reverse pairs in the array.

A reverse pair is a pair (i, j) where 0 <= i < j < nums.length and nums[i] > 2 * nums[j].

Example 1: Input: nums = [1,3,2,3,1]

Output: 2

Example 2: Input: nums = [2,4,3,5,1]

Output: 3

Constraints: 1 <= nums.length <= 5 * 104 -2^31 <= nums[i] <= 2^31 – 1

import java.util.*;

public class Solution {

static class TreapNode {

double key;
 double priority;

TreapNode left, right;

long count;

TreapNode(double key) {

this.key = key;

this.priority = Math.random();

this.count = 1;

long getCount(TreapNode node) {

return node == null ? 0 : node.count;

void updateCount(TreapNode node) {

if (node != null) {

node.count = 1 + getCount(node.left) + getCount(node.right);

TreapNode[] split(TreapNode root, double key) {

if (root == null) return new TreapNode[]{null, null};

if (root.key < key) {

TreapNode[] rightSplit = split(root.right, key);

root.right = rightSplit[0];

updateCount(root);

return new TreapNode[]{root, rightSplit[1]};

} else {

TreapNode[] leftSplit = split(root.left, key);

root.left = leftSplit[1];
 updateCount(root);

return new TreapNode[]{leftSplit[0], root};

TreapNode merge(TreapNode left, TreapNode right) {

if (left == null || right == null) return left != null ? left : right;

if (left.priority > right.priority) {

left.right = merge(left.right, right);

updateCount(left);

return left;

} else {

right.left = merge(left, right.left);

updateCount(right);

return right;

TreapNode insert(TreapNode root, TreapNode node) {

if (root == null) return node;

if (node.priority > root.priority) {

TreapNode[] splitNodes = split(root, node.key);

node.left = splitNodes[0];

node.right = splitNodes[1];

updateCount(node);

return node;

} else if (node.key < root.key) {

root.left = insert(root.left, node);

} else {

root.right = insert(root.right, node);

}
 updateCount(root);

return root;

long countLessThan(TreapNode root, double key) {

TreapNode[] splitNodes = split(root, key);

long count = getCount(splitNodes[0]);

root = merge(splitNodes[0], splitNodes[1]); // restore tree

return count;

public int reversePairs(int[] nums) {

TreapNode root = null;

int count = 0;

for (int i = nums.length - 1; i >= 0; i--) {

count += countLessThan(root, nums[i] / 2.0);

root = insert(root, new TreapNode(nums[i]));

return count;

public static void main(String[] args) {

Scanner sc = new Scanner(System.in);

int n = sc.nextInt();

int[] nums = new int[n];

for (int i = 0; i < n; i++) nums[i] = sc.nextInt();

Solution sol = new Solution();

System.out.println(sol.reversePairs(nums));
 }

Write a JAVA Program to find a permutation of the vertices (topological order) which corresponds to
the order defined by all edges of the graph

Topological sorting for Directed Acyclic Graph (DAG) is a linear ordering of vertices such that for
every directed edge u v, vertex u comes before v in the ordering.

Topological Sorting for a graph is not possible if the graph is not a DAG. For example, a topological
sorting of the following graph is “5 4 2 3 1 0”.

There can be more than one topological sorting for a graph. For example, another topological
sorting of the following graph is “4 5 2 3 1 0”.

The first vertex in topological sorting is always a vertex with in degree as 0 (a vertex with no
incoming edges).

input =

57

02

03

10

13

24

32

34

output =

10324

import java.util.*;

class program

public static void main(String args[])

Scanner sc = new Scanner(System.in);

int n=sc.nextInt();

int e = sc.nextInt();

List<List<Integer>> graph = new ArrayList<>();

graph.add(new ArrayList<>());

int indegree[]=new int[n];

for(int i=0;i<e;i++)

int a=sc.nextInt();

int b=sc.nextInt();

graph.get(a).add(b);

indegree[b]++;

Queue<Integer> q= new LinkedList<>();

for(int i=0;i<n;i++)

if(indegree[i]==0)

q.add(i);

List<Integer> li = new ArrayList<>();

while(!q.isEmpty())

int u=q.poll();

li.add(u);

for(int v : graph.get(u))

indegree[v]--;

if(indegree[v]==0)

{
 q.add(v);

if(li.size()!=n)

System.out.println("cycle");

else

for(int i : li)

System.out.println(i);

Write a JAVA Program to find all the articulation points of a graph Date:____________ We are given
an undirected graph. An articulation point (or cut vertex) is defined as a vertex which, when removed
along with associated edges, makes the graph disconnected (or more precisely, increases the number
of connected components in the graph). The task is to find all articulation points in the given graph.

Given an undirected, connected graph, identify all articulation points in the graph.

An articulation point (or cut vertex) is a vertex that, when removed along with its associated edges,

increases the number of connected components in the graph. These vertices are critical for
maintaining the connectivity of the graph.

Input Format:

------------

- The first line contains two integers V and E — the number of vertices and edges in the graph.

- The next E lines contain two integers u and v — representing an undirected edge between vertex u
and vertex v.
Vertices are numbered from 0 to V - 1.

Output Format:

--------------

- Print a list of articulation points in increasing order.

- If there are no articulation points, print an empty list [].

Constraints:

-------------

- 1≤ V ≤10^4

- 0≤ E ≤10^5

- No self-loops or multiple edges.

Example Input 1:

----------------

55

10

02

21

03

34

Example Output 1:

------------------

[0, 3]

Explanation:

-------------

Removing vertex 0 disconnects 3 and 4 from the rest of the graph.

Removing 3 disconnects 4. So both are articulation points.

-----------------

43

01

12

23

Example Output 2:

-----------------

[1, 2]

Notes:

-------

- The graph may contain multiple components.

- The result should be based on DFS traversal using Tarjan’s algorithm for finding articulation points
efficiently.

import java.util.*;

public class program{

static void dfs(int p, List<List<Integer>> adj, boolean[] v) {

v[p] = true;

for (int x : adj.get(p)) {

if(!v[x]){

dfs(x,adj,v);

static ArrayList<Integer> find(int n,List<List<Integer>> adj) {

ArrayList<Integer> res = new ArrayList<>();

for (int i=0;i<n; i++) {

boolean[] v = new boolean[n];

v[i] = true;
 int c = 0;

for (int x :adj.get(i)) {

if (!v[x]) {

dfs(x,adj,v);

c++;

if(c>1)res.add(i);

return res.isEmpty() ? new ArrayList<>(Arrays.asList(-1)):res;

public static void main(String[] args) {

Scanner sc = new Scanner(System.in);

int n= sc.nextInt();

int e = sc.nextInt();

List<List<Integer>> adj = new ArrayList<>();

for (int i=0;i<n;i++)adj.add(new ArrayList<>());

for(int i=0;i<e;i++){

int u =sc.nextInt();

int v =sc.nextInt();

adj.get(u).add(v);

adj.get(v).add(u);

List<Integer> ans = find(n,adj);

System.out.println(ans);

Write a JAVA Program to check whether the permutation of a string forms a palindrome

Given a string s, return true if a permutation of the string could form a palindrome.

Example 1: Input: s = "code"

Input: s = "aab" Output: true

Example 3: Input: s = "carerac" Output: true

PROGRAM

import java.util.*;

class PermutationPalindrome

public boolean canPermutePalindrome(String s)

Integer bitMask = 0;

for (int i = 0; i < s.length(); i++)

bitMask ^= 1 << (s.charAt(i) - 'a' + 1);

return Integer.bitCount(bitMask) <= 1;

public static void main(String args[])

{ Scanner sc = new Scanner(System.in);

System.out.println(new PermutationPalindrome().canPermutePalindrome(sc.next()));

Write a JAVA Program to return all index pairs [i,j] given a text string and words (a list), so that the
substring text[i]…text[j] is in the list of words

Given a text string and words (a list of strings), return all index pairs [i, j] so that the substring
text[i]...text[j] is in the list of words.

Note: • All strings contains only lowercase English letters.

• It's guaranteed that all strings in words are different.

• Return the pairs [i,j] in sorted order (i.e. sort them by their first coordinate in case of ties sort them
by their second coordinate).

Example 1: Input: text = "thestoryofleetcodeandme",

words = ["story","fleet","leetcode"]

Output: [[3,7],[9,13],[10,17]]

Example 2: Input: text = "ababa",

words = ["aba","ab"]
Output: [[0,1],[0,2],[2,3],[2,4]]

Explanation: Notice that matches can overlap, see "aba" is found in [0,2] and [2,4].

import java.util.*;

public class Solution {

public int[][] indexPairs(String text, String[] words) {

List<int[]> result = new ArrayList<>();

for (String word : words) {

int index = text.indexOf(word);

while (index != -1) {

result.add(new int[]{index, index + word.length() - 1});

index = text.indexOf(word, index + 1);

// Sort by starting index, then ending index

result.sort((a, b) -> a[0] != b[0] ? a[0] - b[0] : a[1] - b[1]);

// Convert List to array

return result.toArray(new int[result.size()][]);

public static void main(String[] args) {

Scanner sc = new Scanner(System.in);

String text = sc.nextLine();

String[] words = sc.nextLine().split(" ");

int[][] res = new Solution().indexPairs(text, words);

for (int[] pair : res) {

System.out.println(Arrays.toString(pair));
 }

Lowest common Ancestor

import java.util.*;

public class Test

public static void main(String[] args)

Scanner sc = new Scanner(System.in);

String[] arr= sc.nextLine().split(" ");

String[] persons = sc.nextLine().split(" ");

List<Integer> v = new ArrayList<>();

int n=arr.length;

for (int i = 0; i < n; i++)

v.add(Integer.parseInt(arr[i]));

Node root = new Node(v.get(0));

Node P1 = new Node(Integer.parseInt(persons[0]));

Node P2 = new Node(Integer.parseInt(persons[1]));

q.add(root);

int j = 1;

while (j < n && !q.isEmpty())

Node temp = q.poll();

if (v.get(j) != -1)

temp.left = new Node(v.get(j));

q.add(temp.left);

j++;

if (j < n && v.get(j) != -1)

temp.right = new Node(v.get(j));

q.add(temp.right);

j++;

Node res=new Solution().lowestCommonAscendant(root, P1, P2);

System.out.println(res.data);

class Node
{

public int data;

public Node left;

public Node right;

public Node(int value)

data = value;

left = null;

right = null;

class Solution

Node lowestCommonAscendant(Node root,Node P1, Node P2){

if (root == null || root.data == P1.data ||

root.data == P2.data)

return root;

Node left = lowestCommonAscendant(root.left, P1, P2);

Node right = lowestCommonAscendant(root.right, P1, P2);

return left == null ? right : right == null ? left : root;

Input=1 2 3 4 5 6 7 8 9 10 11

78

Output=1
Write a JAVA Program to find the Longest Increasing Path in a Matrix. Given an integer matrix, find
the length of the longest increasing path. From each cell, you can either move to four directions: left,
right, up or down. You may NOT move diagonally or move outside of the boundary (i.e. wrap-around
is not allowed).

Input:

nums =3 3

345

326

221

Output: 4

import java.util.*;

public class Solution

private int[] dx = new int[] { 0, 0, -1, 1 };

private int[] dy = new int[] { 1, -1, 0, 0 };

public int longestIncreasingPath(int[][] matrix)

if (matrix == null || matrix.length == 0) { return 0;

int longest = 0;

int m = matrix.length ;

int n = matrix[0].length;

// longest path starting from position (i,j)

int[][] dp = new int[m][n];

for (int i = 0; i < m; i++)

for (int j = 0; j < n; j++)

longest = Math.max(longest, dfs(i, j, matrix, dp));

}
return longest;

private int dfs(int row, int col, int[][] matrix, int[][] dp)

if (dp[row][col] > 0)

return dp[row][col];

int m = matrix.length;

int n = matrix[0].length;

int currentLongest = 0;

for (int c = 0; c < 4; c++)

int i = row + dx[c];

int j = col + dy[c];

if (i >= 0 && i < m && j >= 0 && j < n && matrix[row][col] < matrix[i][j])

currentLongest = Math.max(currentLongest, dfs(i, j, matrix, dp));

dp[row][col] = 1 + currentLongest;

return dp[row][col];

public static void main(String args[])

Scanner sc = new Scanner(System.in);

int m = sc.nextInt();

int n = sc.nextInt();

int matrix[][] = new int[m][n];

for (int j = 0; j < n; j++)

matrix[i][j] = sc.nextInt();

System.out.println(new Solution().longestIncreasingPath(matrix));

Lexographically smallest equivalent string