### Find the maximum sum of any continuous subarray of size K

Introduction You are given an array of integers with size N, and a number K…

October 01, 2020

Replace all spaces in a string with ‘%20’ (three characters). Do this in place and assume you have enough space in array

This is the simplest solution which many people might think.

- Iterate from left side (begining)
- After encountering a space, first shift entire array by 2 places.
- Put
`%20`

at consecutive location - Repeat this process

Obviously, if you see you need to shift the remaining array as many times as number of spaces. And, is not an efficient algorithm.

I will not put this silly code.

The complexity would be close to `O(n^2)`

If you start from left side, you saw we need to shift the array. What if we start from the right side.

- First calculate number of spaces in array, this will help in calculating the resultant last index
- Start iterating from right most side.
- Maintain two index counters. One for original array characters, other for resultant index positions.
- Start copying character one by one.
- If found space, just copy consecutive
`%20`

At the end, you will achieve the purpose. Lets see the code

```
private static int countSpaces(char[] input) {
int c = 0;
for (int i=0; i<input.length; i++) {
if (input[i] == ' ') {
c ++;
}
}
return c;
}
public static int replace(char[] input, int len) {
int spaces = countSpaces(input);
if (spaces == 0) return len;
int lastIndex = (len-1) + (2 * spaces);
int resultIndex = lastIndex;
for (int i=len-1; i>=0; i--) {
if (input[i] == ' ') {
//copy %20
input[lastIndex] = '0';
input[lastIndex-1] = '2';
input[lastIndex-2] = '%';
lastIndex -= 3;
}
else {
//copy actual characters
input[lastIndex] = input[i];
lastIndex --;
}
}
return resultIndex;
}
```

The complexity is `O(n)`

Introduction You are given an array of integers with size N, and a number K…

Problem Statement Implement atoi which converts a string to an integer…

Problem Statement Given a sorted array nums, remove the duplicates in-place such…

This algorithm is very useful for large input. And, is quite efficient one. It…

Sorting Problems Merge Sort Quick Sort Heap Sort Bubble Sort Selection Sort…

A number consists of digits. Example: 843. Its a 3-digit number. Radix sort…

Problem Statement You are given an array prices where prices[i] is the price of…

Introduction In this post we will see: How to prepare a docker image for your…

Introduction We have a page, for example a . And, upon submission we would want…

Problem Statement I have a parent component which loads some list categories…

Introduction This post is in contuation of our previous post: How to use Draft…

Introduction In this post, we will use in Next.js with strapi. And, we will…