DEV Community: Harsh Rajpal

CodiumAI's PR-Agent vs. GitHub Copilot for Pull Requests: Elevating Code Collaboration and Quality in Depth

Harsh Rajpal — Sun, 24 Dec 2023 09:59:32 +0000

In the dynamic landscape of modern software development, the tools developers choose significantly influence the efficiency, collaboration, and overall quality of the code they produce. CodiumAI's PR-Agent and GitHub Copilot for Pull Requests are two AI-powered code assistance tools that have garnered attention in this space. In this detailed comparison, we will explore the nuanced features of PR-Agent that position it as a superior choice over GitHub Copilot for Pull Requests, focusing on its command capabilities, platform support, open-source nature, and providing real-world examples to illustrate its practical advantages.

1. Command Capabilities: PR-Agent's Versatility vs. GitHub Copilot for PR’s Singular Focus

PR-Agent:
CodiumAI's PR-Agent distinguishes itself with an extensive set of commands designed to address various aspects of the development process, specifically within the context of pull requests. Developers can leverage commands like /review, /describe, /ask, /improve, and /generate_labels to perform nuanced tasks, from detailed code reviews to seeking clarification and suggesting improvements. This breadth of command capabilities empowers developers with fine-grained control over the tool, facilitating a more comprehensive approach to code collaboration in pull requests.

GitHub Copilot for PR:
GitHub Copilot for Pull Requests currently provides a single command that primarily focuses on code completion within the context of pull requests. While adept at generating code snippets, the tool lacks the multifaceted command set offered by PR-Agent, limiting its versatility in addressing diverse developer needs throughout the pull request lifecycle.

2. Platform Support: PR-Agent's Inclusivity vs. GitHub Copilot for PRs' Limitation

PR-Agent:
A notable strength of PR-Agent lies in its inclusive approach to platform support. It seamlessly integrates with a variety of Git platforms, including GitHub, GitLab, Bitbucket, CodeCommit, and Azure DevOps. This broad platform compatibility ensures that development teams are not restricted to a specific version control system, promoting flexibility and collaboration across various ecosystems, specifically within the context of pull requests.

GitHub Copilot for PR:
GitHub Copilot for Pull Requests, while powerful in its own right, is confined to the GitHub platform. This limitation may pose challenges for teams working with different Git platforms, limiting their ability to uniformly leverage the tool across their pull request workflows.

3. Open Source Advantage: PR-Agent's Transparency and Community Involvement

PR-Agent:
PR-Agent's open-source nature is a significant advantage that fosters transparency and community involvement, specifically in the realm of pull requests. The tool's code is publicly accessible on GitHub (PR-Agent GitHub Repository), allowing developers to inspect, contribute, and provide feedback. This open collaboration model encourages a sense of ownership and engagement, with developers actively participating in shaping the tool's features and capabilities within the context of pull requests.

GitHub Copilot for PR:
In contrast, GitHub Copilot for Pull Requests is a proprietary solution, limiting the transparency and community involvement that is intrinsic to open-source projects like PR-Agent. Users depend on GitHub for updates and improvements, without the direct ability to contribute to the tool's development specifically within the context of pull requests.

4. Learning and Adaptability: PR-Agent's Context-Aware Commands vs. GitHub Copilot's Code Autocompletion

PR-Agent:
CodiumAI's PR-Agent incorporates context-aware commands that leverage machine learning to understand the specific context of a pull request. This allows developers to use commands that are more intuitive and contextually relevant. For example, the /review command might analyze code changes and provide feedback, taking into account the scope and impact of the changes. This level of intelligence in command execution enhances the tool's adaptability to different scenarios within the pull request workflow, providing a more tailored and nuanced user experience.

GitHub Copilot for PR:
GitHub Copilot, on the other hand, excels at code autocompletion by generating code snippets based on patterns learned from a vast codebase. While powerful for coding efficiency, it may lack the contextual understanding that PR-Agent brings to the table. GitHub Copilot's strength lies in assisting with code generation, but it might not provide the same level of sophistication when it comes to executing context-aware commands for various pull request tasks beyond code completion.

5. Extensibility: PR-Agent's Customization Options vs. GitHub Copilot's Fixed Functionality

PR-Agent:
PR-Agent distinguishes itself with customization options, allowing development teams to tailor the tool to their specific workflow and preferences. Teams can potentially extend the functionality by adding custom commands or integrating additional tools, enhancing the tool's adaptability to diverse development environments.

GitHub Copilot for PR:
GitHub Copilot, being a closed-source solution, may have limitations in terms of customization and extensibility. Teams using GitHub Copilot might have less flexibility in adapting the tool to their unique processes and may need to conform to the fixed functionality provided by the tool.

Feature Comparison

Real-World Examples: Demonstrating PR-Agent's Practical Value

In the ever-evolving landscape of software development, CodiumAI's PR-Agent emerges as a versatile ally, empowering developers with a rich set of tools for code collaboration, review, and enhancement. Let's explore real-world examples that highlight PR-Agent's practical value, showcasing how it excels in addressing common challenges faced by development teams.

PR-Agent's extensive set of commands empowers developers to address a spectrum of development tasks with precision. Unlike solutions with a singular focus, PR-Agent offers commands like /review, /describe, /ask, /improve and /generate_labels.

Let's delve into the nuanced capabilities of two essential commands: /review and /generate_labels.

The Power of /review

The /review command in PR-Agent stands as a cornerstone for comprehensive pull request analysis. Developers can deploy this command to initiate a thorough examination of specific pull request changes. Witness its influence in action:

In this scenario, the developer invokes PR-Agent to scrutinize the intricacies of the latest pull request's changes. PR-Agent, armed with its advanced language model, conducts a holistic evaluation. It offers constructive feedback, identifies potential issues, and suggests improvements. This nuanced guidance empowers developers to understand specific aspects requiring attention, fostering a collaborative environment for continuous refinement in the pull request lifecycle.

Unleashing the Potential of /generate_labels

Efficiency in pull request management hinges on streamlined labeling processes, and PR-Agent excels in this domain with the /generate_labels command. Witness its seamless integration:

Here, the developer tasks PR-Agent with intelligently assigning labels to the latest pull request. PR-Agent, leveraging its contextual understanding of code changes, automatically categorizes the pull request with relevant labels. This automation accelerates the labeling process, ensuring pull requests are appropriately tagged. The outcome is an organized workflow, enhancing team productivity and preserving clarity in project management without manual intervention.

PR-Agent's nuanced understanding of commands allows it to deliver targeted and relevant insights, catering to the diverse needs of developers throughout the development lifecycle.

Conclusion: PR-Agent's Holistic Approach to Code Collaboration

In conclusion, CodiumAI's PR-Agent emerges as a robust and versatile solution for developers and teams seeking a comprehensive approach to code collaboration, review, and improvement, specifically within the context of pull requests. Its rich command set, broad platform support, open-source ethos, and availability both on Git and IDE collectively position it as a superior choice over GitHub Copilot for Pull Requests. By choosing PR-Agent, developers not only streamline their workflow but actively participate in a tool's evolution, fostering a culture of continuous improvement and collaboration. Experience the future of code quality with PR-Agent, where versatility meets transparency and community-driven development.

26. Remove Duplicates from Sorted Array

Harsh Rajpal — Thu, 18 May 2023 09:19:07 +0000

Question Statement:
Given an integer array nums sorted in non-decreasing order, remove the duplicates in-place such that each unique element appears only once. The relative order of the elements should be kept the same. Then return the number of unique elements in nums.

Consider the number of unique elements of nums to be k, to get accepted, you need to do the following things:

Change the array nums such that the first k elements of nums contain the unique elements in the order they were present in nums initially. The remaining elements of nums are not important as well as the size of nums.
Return k.

Custom Judge:

The judge will test your solution with the following code:

int[] nums = [...]; // Input array
int[] expectedNums = [...]; // The expected answer with correct length

int k = removeDuplicates(nums); // Calls your implementation

assert k == expectedNums.length;
for (int i = 0; i < k; i++) {
    assert nums[i] == expectedNums[i];
}

If all assertions pass, then your solution will be accepted.

Example 1:
Input: nums = [1,1,2]
Output: 2, nums = [1,2,_]
Explanation: Your function should return k = 2, with the first two elements of nums being 1 and 2 respectively.
It does not matter what you leave beyond the returned k (hence they are underscores).

Example 2:
Input: nums = [0,0,1,1,1,2,2,3,3,4]
Output: 5, nums = [0,1,2,3,4,,,,,_]
Explanation: Your function should return k = 5, with the first five elements of nums being 0, 1, 2, 3, and 4 respectively.
It does not matter what you leave beyond the returned k (hence they are underscores).

Constraints:

1 <= nums.length <= 3 * 104
-100 <= nums[i] <= 100
nums is sorted in non-decreasing order.

Solution:

class Solution {
    public int removeDuplicates(int[] nums) {
int i=0;
        for(int j=1;j<nums.length;j++){
            if(nums[i]!=nums[j]){
                i++;
                nums[i]=nums[j];
            }    
        }

        return i+1;
    }
}

1752. Check if Array Is Sorted and Rotated

Harsh Rajpal — Thu, 18 May 2023 08:27:50 +0000

Given an array nums, return true if the array was originally sorted in non-decreasing order, then rotated some number of positions (including zero). Otherwise, return false.

There may be duplicates in the original array.

Note: An array A rotated by x positions results in an array B of the same length such that A[i] == B[(i+x) % A.length], where % is the modulo operation.

Example 1:
Input: nums = [3,4,5,1,2]
Output: true
Explanation: [1,2,3,4,5] is the original sorted array.
You can rotate the array by x = 3 positions to begin on the the element of value 3: [3,4,5,1,2].

Example 2:
Input: nums = [2,1,3,4]
Output: false
Explanation: There is no sorted array once rotated that can make nums.

Example 3:
Input: nums = [1,2,3]
Output: true
Explanation: [1,2,3] is the original sorted array.
You can rotate the array by x = 0 positions (i.e. no rotation) to make nums.

Constraints:

1 <= nums.length <= 100
1 <= nums[i] <= 100

Solution:

class Solution {
    public boolean check(int[] n) {
        int l= n.length; // Calculating length of given array.
        int nRotation=0;// Declaring a variable to keep a count of number of rotations.
//Running a for loop to identify any rotation in given array.
        for(int i=0;i<l;i++){
            if(n[i]>n[(i+1)%l]){
                nRotation++;
            }
        }
//If number of rotations are greater than 1 return false.
        if(nRotation>1)
            return false;
//Else return True.
        return true;

    }
}

2306. Naming a Company

Harsh Rajpal — Thu, 09 Feb 2023 03:53:42 +0000

Problem Statement:

You are given an array of strings ideas that represents a list of names to be used in the process of naming a company. The process of naming a company is as follows:

Choose 2 distinct names from ideas, call them ideaA and ideaB.
Swap the first letters of ideaA and ideaB with each other.
If both of the new names are not found in the original ideas, then the name ideaA ideaB (the concatenation of ideaA and ideaB, separated by a space) is a valid company name.
Otherwise, it is not a valid name.
Return the number of distinct valid names for the company.

Example 1:

Input: ideas = ["coffee","donuts","time","toffee"]
Output: 6
Explanation: The following selections are valid:

("coffee", "donuts"): The company name created is "doffee conuts".
("donuts", "coffee"): The company name created is "conuts doffee".
("donuts", "time"): The company name created is "tonuts dime".
("donuts", "toffee"): The company name created is "tonuts doffee".
("time", "donuts"): The company name created is "dime tonuts".
("toffee", "donuts"): The company name created is "doffee tonuts". Therefore, there are a total of 6 distinct company names.

The following are some examples of invalid selections:

("coffee", "time"): The name "toffee" formed after swapping already exists in the original array.
("time", "toffee"): Both names are still the same after swapping and exist in the original array.
("coffee", "toffee"): Both names formed after swapping already exist in the original array.

Example 2:

Input: ideas = ["lack","back"]
Output: 0
Explanation: There are no valid selections. Therefore, 0 is returned.

Constraints:

2 <= ideas.length <= 5 * 104
1 <= ideas[i].length <= 10
ideas[i] consists of lowercase English letters.
All the strings in ideas are unique.

Solution:

Code:

class Solution {


    public long distinctNames(String[] ideas) {
        long ans = 0;
        Map<Character, Set<String>> map = new HashMap<>();
        for (String idea : ideas) {
            char startChar = idea.charAt(0);
            Set<String> values = map.getOrDefault(startChar, new HashSet<>());
            values.add(idea.substring(1));
            map.put(startChar, values);
        }
        for (int i = 0; i <= 26; i++) {
            for (int j = i + 1; j <= 26; j++) {
                long unique = count(map, (char) (i + 'a'), (char) (j + 'a'));
                ans += unique;
            }
        }
        return ans;


    }
     private long count(Map<Character, Set<String>> map, char a, char b) {
        if (!map.containsKey(a) || !map.containsKey(b)) {
            return 0;
        }
        long common = 0;
        Set<String> first = map.get(a);
        Set<String> second = map.get(b);
        for (String c : first) {
            if (second.contains(c)) {
                common++;
            }
        }
        long uniqueA = first.size() - common;
        long uniqueB = second.size() - common;
        return uniqueA * uniqueB * 2L;
    }
}

472. Concatenated Words

Harsh Rajpal — Fri, 27 Jan 2023 03:46:19 +0000

Problem Statement:

Given an array of strings words (without duplicates), return all the concatenated words in the given list of words.

A concatenated word is defined as a string that is comprised entirely of at least two shorter words in the given array.

Example 1:

Input: words = ["cat","cats","catsdogcats","dog","dogcatsdog","hippopotamuses","rat","ratcatdogcat"]

Output: ["catsdogcats","dogcatsdog","ratcatdogcat"]
Explanation: "catsdogcats" can be concatenated by "cats", "dog" and "cats";
"dogcatsdog" can be concatenated by "dog", "cats" and "dog";
"ratcatdogcat" can be concatenated by "rat", "cat", "dog" and "cat".

Example 2:

Input: words = ["cat","dog","catdog"]
Output: ["catdog"]

Constraints:

1 <= words.length <= 104
1 <= words[i].length <= 30
words[i] consists of only lowercase English letters.
All the strings of words are unique.
1 <= sum(words[i].length) <= 105

Solution:

Code:

class Solution {
  public List<String> findAllConcatenatedWordsInADict(String[] words) {
    List<String> ans = new ArrayList<>();
    Set<String> wordSet = new HashSet<>(Arrays.asList(words));
    Map<String, Boolean> memo = new HashMap<>();

    for (final String word : words)
      if (wordBreak(word, wordSet, memo))
        ans.add(word);

    return ans;
  }

  private boolean wordBreak(final String word, Set<String> wordSet, Map<String, Boolean> memo) {
    if (memo.containsKey(word))
      return memo.get(word);

    for (int i = 1; i < word.length(); ++i) {
      final String prefix = word.substring(0, i);
      final String suffix = word.substring(i);
      if (wordSet.contains(prefix) &&
          (wordSet.contains(suffix) || wordBreak(suffix, wordSet, memo))) {
        memo.put(word, true);
        return true;
      }
    }

    memo.put(word, false);
    return false;
  }
}

787. Cheapest Flights Within K Stops

Harsh Rajpal — Thu, 26 Jan 2023 08:39:41 +0000

Problem Statement:

There are n cities connected by some number of flights. You are given an array flights where flights[i] = [fromi, toi, pricei] indicates that there is a flight from city fromi to city toi with cost pricei.

You are also given three integers src, dst, and k, return the cheapest price from src to dst with at most k stops. If there is no such route, return -1.

Example 1:
Input: n = 4, flights = [[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]], src = 0, dst = 3, k = 1
Output: 700
Explanation:
The graph is shown above.
The optimal path with at most 1 stop from city 0 to 3 is marked in red and has cost 100 + 600 = 700.
Note that the path through cities [0,1,2,3] is cheaper but is invalid because it uses 2 stops.

Example 2:
Input: n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 1
Output: 200
Explanation:
The graph is shown above.
The optimal path with at most 1 stop from city 0 to 2 is marked in red and has cost 100 + 100 = 200.

Example 3:

Input: n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 0
Output: 500
Explanation:
The graph is shown above.
The optimal path with no stops from city 0 to 2 is marked in red and has cost 500.

Constraints:

1 <= n <= 100
0 <= flights.length <= (n * (n - 1) / 2)
flights[i].length == 3
0 <= fromi, toi < n
fromi != toi
1 <= pricei <= 104
There will not be any multiple flights between two cities.
0 <= src, dst, k < n
src != dst

Solution:

Algorithm:

Create a 2D array of size (k+2) * n
Fill the first row with 0 and rest with Integer.MAX_VALUE
Iterate over the flights array and update the dp array
Return the minimum value in the last row

Code:

class Solution {
    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {

        int[][] dp = new int[k+2][n];
        for(int i=0; i<k+2; i++){
            Arrays.fill(dp[i], Integer.MAX_VALUE);
        }
        dp[0][src] = 0;
        for(int i=1; i<k+2; i++){
            for(int[] flight: flights){
                int from = flight[0];
                int to = flight[1];
                int price = flight[2];
                if(dp[i-1][from] != Integer.MAX_VALUE){
                    dp[i][to] = Math.min(dp[i][to], dp[i-1][from] + price);
                }
            }
        }
        int res = Integer.MAX_VALUE;
        for(int i=1; i<k+2; i++){
            res = Math.min(res, dp[i][dst]);
        }
        return res == Integer.MAX_VALUE ? -1 : res;
    }
}

Time Complexity:
O(n^2)
Space Complexity:
O(n^2)

997. Find the Town Judge

Harsh Rajpal — Mon, 23 Jan 2023 09:38:34 +0000

Problem Statement:

In a town,there are n people labeled from 1 to n.There is a rumor that one of these people is secretly the town judge.

If the town judge exists,then:

The town judge trusts nobody.Everybody(except for the town judge)trusts the town judge.There is exactly one person that satisfies properties 1 and 2. You are given an array trust where trust[i]=[ai,bi]representing that the person labeled ai trusts the person labeled bi.

Return the label of the town judge if the town judge exists and can be identified,or return-1 otherwise.

Example 1:

Input: n=2,trust=[[1,2]]
Output:2

Example 2:

Input: n=3,trust=[[1,3],[2,3]]
Output:3

Example 3:

Input: n=3,trust=[[1,3],[2,3],[3,1]]
Output:-1

Constraints:

1<=n<=1000 0<=trust.length<=104 trust[i].length==2
All the pairs of trust are unique.ai!=bi 1<=ai,bi<=n

Solution:
Algorithm:

Create two arrays inDegree and outDegree.
Traverse the trust array and update the inDegree and outDegree arrays.
Traverse the inDegree array and check if the current person is the town judge.
If the current person is the town judge, return the current person.
If the town judge does not exist, return -1.

Code:

public class Solution {
    public int findJudge(int n, int[][] trust) {
        int[] inDegree = new int[n + 1];
        int[] outDegree = new int[n + 1];
        for (int[] t : trust) {
            outDegree[t[0]]++;
            inDegree[t[1]]++;
        }
        for (int i = 1; i <= n; i++) {
            if (inDegree[i] == n - 1 && outDegree[i] == 0) {
                return i;
            }
        }
        return -1;
    }
}

Time Complexity:
O(n)O(n) The time complexity is linear, because we traverse the trust array once.

Space Complexity:
O(n)O(n) The space complexity is linear, because we create two arrays of size n+1.

131. Palindrome Partitioning

Harsh Rajpal — Sun, 22 Jan 2023 15:12:12 +0000

Problem Statement:

Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s.

Example 1:

Input: s = "aab"
Output: [["a","a","b"],["aa","b"]]

Example 2:

Input: s = "a"
Output: [["a"]]

Constraints:

1 <= s.length <= 16
s contains only lowercase English letters.

Solution:

Algorithm:

Use DFS to traverse all the possible partitions.
Use a helper function to check if the current substring is a palindrome.
If the current substring is a palindrome, add it to the path and continue to traverse the rest of the string.
If the current substring is not a palindrome, do not add it to the path and continue to traverse the rest of the string.
If the current index is equal to the length of the string, add the current path to the result.
After the traversal is completed, return the result.

Code:

public class Solution {
    public List<List<String>> partition(String s) {
        List<List<String>> res = new ArrayList<>();
        List<String> path = new ArrayList<>();
        dfs(s, 0, path, res);
        return res;

    }

    private void dfs(String s, int index, List<String> path, List<List<String>> res) {
        if (index == s.length()) {
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = index; i < s.length(); i++) {
            if (isPalindrome(s, index, i)) {
                path.add(s.substring(index, i + 1));
                dfs(s, i + 1, path, res);
                path.remove(path.size() - 1);
            }
        }
    }

    private boolean isPalindrome(String s, int left, int right) {
        while (left < right) {
            if (s.charAt(left) != s.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }

}

Time Complexity:
O(n*2^n)O(n∗2n) The time complexity of the backtracking algorithm is exponential, because in the worst case, we need to add n-1 separators into a string of length n, which results in 2^n2

Space Complexity:
O(n)O(n) The space complexity of the backtracking algorithm is linear, because in the worst case, the depth of the recursion tree can reach nn.

59. Spiral Matrix II

Harsh Rajpal — Thu, 19 Jan 2023 05:14:04 +0000

Problem Statement:

Given a positive integer n, generate an n x n matrix filled with elements from 1 to n2 in spiral order.

Example 1:
Input: n = 3
Output: [[1,2,3],[8,9,4],[7,6,5]]

Example 2:
Input: n = 1
*Output: *[[1]]

Constraints:

1 <= n <= 20

Solution:

Algorithm:

Create a matrix of size n x n.
Initialize left = 0, right = n - 1, top = 0, bottom = n - 1, num = 1
Iterate while left <= right and top <= bottom. a) Iterate from left to right and fill the top row with num. b) Increment top. c) Iterate from top to bottom and fill the right column with num. d) Decrement right. e) Iterate from right to left and fill the bottom row with num. f) Decrement bottom. g) Iterate from bottom to top and fill the left column with num. h) Increment left.
Return matrix.

Code:

public class Solution {
    public int[][] generateMatrix(int n){
        int[][] matrix = new int[n][n];
        int left = 0;
        int right = n - 1;
        int top = 0;
        int bottom = n - 1;
        int num = 1;
        while(left <= right && top <= bottom){
            for(int i = left; i <= right; i++){
                matrix[top][i] = num++;
            }
            top++;
            for(int i = top; i <= bottom; i++){
                matrix[i][right] = num++;
            }
            right--;
            for(int i = right; i >= left; i--){
                matrix[bottom][i] = num++;
            }
            bottom--;
            for(int i = bottom; i >= top; i--){
                matrix[i][left] = num++;
            }
            left++;
        }
    }
}

Time Complexity:
O(N^2)

Space Complexity:
O(N^2)

974. Subarray Sums Divisible by K

Harsh Rajpal — Thu, 19 Jan 2023 04:16:40 +0000

Problem Statement:
Given an integer array nums and an integer k, return the number of non-empty subarrays that have a sum divisible by k.

A subarray is a contiguous part of an array.

Example 1:

Input: nums = [4,5,0,-2,-3,1], k = 5
Output: 7
Explanation: There are 7 subarrays with a sum divisible by k = 5:
[4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3]

Example 2:

Input: nums = [5], k = 9
Output: 0

Constraints:

1 <= nums.length <= 3 * 104
-104 <= nums[i] <= 104
2 <= k <= 104

Solution:

Algorithm:

Create a count array of size k and initialize all elements as 0.
Initialize sum of elements as 0 and count of subarrays as 0.
Iterate through the array and for every element arr[i], do following. a) Increment sum by arr[i]. b) If k is non-zero, then update sum as sum = sum % k. c) Increment count of current sum. d) Add count[sub_sum] to the result. e) Increment count[sub_sum] by 1.
Return result.

Code:

public class Solution {
    public int subarrayDivByK(int[] nums, int k){
        int[] count = new int[k];
        count[0] = 1;
        int sum = 0;
        int ans = 0;
        for(int i = 0; i < nums.length; i++){
            sum += nums[i];
            int mod = (sum % k + k) % k;
            ans += count[mod];
            count[mod]++;
        }
        return ans;
    }

}

Time Complexity:
O(N)
Space Complexity:
O(K)

234. Palindrome Linked List

Harsh Rajpal — Tue, 17 Jan 2023 10:29:16 +0000

Problem Statement:

Given the head of a singly linked list, return true if it is a
palindrome or false otherwise.

Example 1:

Input: head = [1,2,2,1]
Output: true

Example 2:

Input: head = [1,2]
Output: false

Constraints:

The number of nodes in the list is in the range [1, 105].
0 <= Node.val <= 9

Solution:

Code:

public class Solution {
    public boolean isPalindrome(ListNode head) {
        ListNode slow = head, fast = head, prev, temp;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        prev = slow;
        slow = slow.next;
        prev.next = null;
        while (slow != null) {
            temp = slow.next;
            slow.next = prev;
            prev = slow;
            slow = temp;
        }
        fast = head;
        slow = prev;
        while (slow != null) {
            if (fast.val != slow.val)
                return false;
            fast = fast.next;
            slow = slow.next;
        }
        return true;
    }

}

926. Flip String to Monotone Increasing

Harsh Rajpal — Tue, 17 Jan 2023 04:09:08 +0000

Problem Statement:

A binary string is monotone increasing if it consists of some number of 0's (possibly none), followed by some number of 1's (also possibly none).

You are given a binary string s. You can flip s[i] changing it from 0 to 1 or from 1 to 0.

Return the minimum number of flips to make s monotone increasing.

Example 1:
Input: s = "00110"
Output: 1
Explanation: We flip the last digit to get 00111.

Example 2:
Input: s = "010110"
Output: 2
Explanation: We flip to get 011111, or alternatively 000111.

Example 3:

Input: s = "00011000"
Output: 2
Explanation: We flip to get 00000000.

Constraints:

1 <= s.length <= 105
s[i] is either '0' or '1'.

Solution:

Code:

class Solution {
    public int minFlipsMonoIncr(String s) {
        int n = s.length();
        int flipCount = 0;
        int oneCount = 0;
        for (int i = 0; i < n; i++) {
            if (s.charAt(i) == '0') {
                if (oneCount == 0)
                    continue;
                flipCount++;
            } else
                oneCount++;
            if (oneCount < flipCount)
                flipCount = oneCount;
        }
        return flipCount;

    }
}

Time Complexity:
O(N)
Space Complexity:
O(1)