Assignment-01

Title: Array-Problems
Name: P. Jaswanth

Roll No: S20220010168

DSA Batch: 1
Date: 24/05/2025

Q1. Array Intersection

Solution:

import java.util.*;

public class IntersectionOfArrays {

public static int[] intersection(int[] nums1, int[] nums2) {
Map<Integer, Integer> map = new HashMap<>();
List<Integer> result = new ArrayList<>();

for (int num : nums1) {

map.put(num, 1);
}

for (int num : nums2) {

if (map.containsKey(num) && map.get(num) == 1) {
result.add(num);
map.put(num, 0);
}
}

int[] answer = new int[result.size()];

for (int i = 0; i < result.size(); i++) {
answer[i] = result.get(i);
}
return answer;

Assignment-01 1
 }

public static void main(String[] args) {

int[] nums1 = {4, 9, 5};
int[] nums2 = {9, 4, 9, 8, 4};

int[] result = intersection(nums1, nums2);

System.out.print("Output: [");
for (int i = 0; i < result.length; i++) {
System.out.print(result[i]);
if (i < result.length - 1) System.out.print(", ");
}
System.out.println("]");
}
}

Dry-Run:

Assignment-01 2
 Q2. Longest Subarray with Sum K
Solution:

public class LongestSubarraySumK {

public static int longestSubarrayWithSumK(int[] arr, int k) {
int i = 0, j = 0;
int sum = 0, maxLength = 0;

while (j < arr.length) {

sum += arr[j];
while (sum > k && i <= j) {
sum -= arr[i];
i++;
}

if (sum == k) {
maxLength = Math.max(maxLength, j - i + 1);
}
j++;
}
return maxLength;
}

public static void main(String[] args) {

int[] arr = {1, 1, 2, 3, 5, 4};
int k = 3;
int result = longestSubarrayWithSumK(arr, k);
System.out.println("Length of longest subarray with sum " + k + " is: "
+ result);
}
}

Dry-Run:

Assignment-01 3
 Q3. Sliding Window Maximum
(Note: The below code seems more related to graph traversal and coloring —
let me know if you'd like a different implementation.)

Solution:

class Solution {
public int largestPathValue(String colors, int[][] edges) {
HashMap<Integer, List<Integer>> graph = new HashMap<>();
int n = colors.length();
int inDegree[] = new int[n];

for (int edge[] : edges) {

graph.computeIfAbsent(edge[0], k -> new ArrayList<>()).add(edge
[1]);

Assignment-01 4
 inDegree[edge[1]]++;
}

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

for (int i = 0; i < n; i++) {
if (inDegree[i] == 0) {
q.offer(i);
}
}

int count[][] = new int[n][26];

int ans = 0, nodeSeen = 0;

while (!q.isEmpty()) {
int node = q.poll();
ans = Math.max(ans, ++count[node][colors.charAt(node) - 'a']);
nodeSeen++;

if (!graph.containsKey(node)) continue;

for (int neighbour : graph.get(node)) {

for (int i = 0; i < 26; i++) {
count[neighbour][i] = Math.max(count[node][i], count[neighbo
ur][i]);
}
inDegree[neighbour]--;
if (inDegree[neighbour] == 0) {
q.offer(neighbour);
}
}
}

return nodeSeen < n ? -1 : ans;

}
}

Dry-Run:

Assignment-01 5
Assignment-01 6
 Q4. Product of Array Except Self
Solution:

import java.util.*;

public class ProductExceptSelf {

public static int[] productSelf(int[] nums) {
int[] result = new int[nums.length];

for (int i = 0, temp = 1; i < nums.length; i++) {

result[i] = temp;
temp *= nums[i];
}

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

result[i] *= temp;
temp *= nums[i];
}

return result;
}

public static void main(String[] args) {

int[] nums = {1, 2, 3, 4};
int[] output = productSelf(nums);

System.out.print("Output: [");
for (int i = 0; i < output.length; i++) {
System.out.print(output[i]);

Assignment-01 7
 if (i < output.length - 1) System.out.print(", ");
}
System.out.println("]");
}
}

Dry-Run:

Q5. Maximum Points on a Line

Solution:

import java.util.*;

public class MaxPoints {

public static int maxPoints(int[][] points) {
int max = 0;

Assignment-01 8
 for (int[] x : points) {
Map<Double, Integer> map = new HashMap<>();

for (int[] y : points) {

if (x == y) continue;

double slope;
if (x[0] == y[0]) {
slope = Double.POSITIVE_INFINITY;
} else {
slope = (y[1] - x[1]) / (double)(y[0] - x[0]);
}

map.put(slope, map.getOrDefault(slope, 0) + 1);

max = Math.max(max, map.get(slope));
}
}

return max + 1;
}

public static void main(String[] args) {

int[][] points = {{1, 1}, {2, 2}, {3, 3}};
System.out.println("Output: " + maxPoints(points));
}
}

Dry-Run:

Assignment-01 9
 Q6. Subarray Product Less Than K
Solution:

public class SubArray {

public int numSubarrayProductLessThanK(int[] nums, int k) {
if (k <= 1) return 0;

int totalCount = 0;
int product = 1;

for (int left = 0, right = 0; right < nums.length; right++) {

product *= nums[right];

while (product >= k) {

product /= nums[left++];
}

Assignment-01 10
 totalCount += right - left + 1;
}

return totalCount;
}

public static void main(String[] args) {

SubArray obj = new SubArray();

int[] nums = {10, 5, 2, 6};

int k = 100;

int output = obj.numSubarrayProductLessThanK(nums, k);

System.out.println("Output: " + output);
}
}

Dry-Run:

Assignment-01 11
 Q7. Maximum Product Subarray
Solution:

public class MaxProductSubarray {

public int maxProduct(int[] nums) {
int n = nums.length;
int result = nums[0];
int curr_max = nums[0];
int curr_min = nums[0];

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

int prev_max = curr_max;

curr_max = Math.max(nums[i], Math.max(curr_max * nums[i], curr_

Assignment-01 12
 min * nums[i]));
curr_min = Math.min(nums[i], Math.min(prev_max * nums[i], curr_mi
n * nums[i]));

result = Math.max(result, curr_max);

}

return result;
}

public static void main(String[] args) {

MaxProductSubarray obj = new MaxProductSubarray();
int[] nums = {2, 3, -2, 4};
int output = obj.maxProduct(nums);
System.out.println("Output: " + output);
}
}

Dry-Run:

Assignment-01 13
Assignment-01 14