Hello Code Recipian! In our previous article  we solved the two sum problem. This is another article in the series leetcode problem solutions  and this article is a solution to leetcode 3  problem. Problem Statement For a given input string s, return the length of the longest substring in s without repeating characters. s consists of English letters and digits. Example 1: Input: s = "abcabcbb" Output: 3 Example 2: Input: s = "bbbbb" Output: 1 Example 3: Input: s = "pwwkew" Output: 3 Solution: Longest Substring Without Repeating Characters Let us try to understand the problem statement first. This is a pretty straightforward problem if you know what a substring is for a given string. A substring a continuous sequence of characters in a given string. For example, the substrings of string "abcd" are: "a", "ab", "abc", "abcd", "b", "bc", "bcd", "c", "cd" and "d". If the characters are not continuous it is not considered a substring. "bd", "ad", "acd" etc. are not substrings because the characters are not continuous as compared to the original string s. Note : Substring is different from a subsequence which may not be consecutive in nature. Now that we know what a substring is, we need to write an algorithm that returns the length of the longest substring in string s . But wait, remember we cannot just return any substring that is longest as clearly mentioned in the problem statement, we are only allowed to consider substrings without repeating characters. "Substring without repeating characters" is nothing but a substring containing all unique characters, there should not be any duplicate characters/letters in the substring. This problem can be efficiently solved by using the two pointer sliding window technique. We slide the window forward each time we find a duplicate character. In this approach we need to process each character in the given string only once to find out the result. Algorithm For a given input string s this algorithm does the following steps: We take two variables start and end to indicate the start and end of the window. The string between the start and end is our current substring. Initially both start and end point to the 0th index (1st character) of the string s , i.e. start = 0 and end = 0. Also create a result variable to store the required result. Next we create a hashmap which helps us to efficiently check if the current substring contains any duplicate characters. Lets name it charIndexMap . Key to this hashmap is the current character and value of this hashmap is the position of the character represented by the hashmap key in the given string s . In each iteration we check if the current character at end index is present in the charIndexMap or not. If the character is not present, add it to the hashmap along with the index. If the character is present in the map already, it means that the current character is a duplicate and we should not be considering the substring with this character while calculating the result. So, take the length of the substring from the start of the window until the previous character. If the current length is greater than the result, update the result. Also since we have found a duplicate character, we need to update the start index. Another important step here is to remove all characters from the previous window from our hashmap (since we have moved our window by updating the start variable). Finally add the current character to our hashmap along with its index. How do we update the start variable once a duplicate character is found? Remember along with storing the characters in hashmap, we also store the index of the character in the string as hashmap value. When we get a duplicate character during our iteration what does this value in hashmap mean? It simply means that the current duplicate character was earlier found at this index represented by the hashmap value (first occurrence). Using this info we discard all the characters before the first occurrence of the duplicate including the first occurrence (discard all characters from previous window). So our new start value will be start = map [current character] + 1. Note : Character literals are represented by uint8 or rune datatype in go.\ Want to master coding? Looking to learn new skills and crack interviews? We recommend you to explore these tailor made courses: Udemy Video Tutorials - Available at 95% off System Design Interview Complete Guide Cracking The Coding Interview - Most Preferred Book For Coding Interviews Data Structures And Algorithms - A Complete Guide   Learn In-Demand Tech Skills And Stay Ahead Of Others Simulation Lets see the working of the above algorithm with an example: Consider s = "abcabcbb" is the given string. Initially start = 0 and end = 0 and our hashmap is empty as shown in the figure below. Also we initialize result = 0. Now we check if s [ end ] = 'a' is present in our hashmap. Obviously 'a' is not present in hashmap, so we add 'a' as hashmap key and 0 as hashmap value indicating 'a' is found at 0th position in string (index based position). Same is shown in figure below: Next we increment end pointer. Again check if s [ end ] = 'b' is present in map. As 'b' is not present we add it to hashmap as shown in diagram below. Increment the end pointer, s [ end ] = 'c', and since it is not in map we add it to our hashmap. Increment end again. Now s [ end ] = 'a'. Now s [ end ]='a' is present in map, which means it is a duplicate character. Since we are looking only for substrings without repeating characters, we cannot consider the current substring "abca" for our result, so our valid substring is only till the previous character, i.e "abc". Since we have found a duplicate the next step is to update result. result = max( result , length of substring from index 0 to 2) = max( result , length of substring "abc") = max (3,3) = 3. Also since the current character is a duplicate, we need to update out start pointer. We update start as start = first occurrence of duplicate + 1 . We can get the first occurrence of duplicate from our hashmap. So start = map ['a'] + 1 = 0+1 = 1. Next, remove all the characters before our new start index and previous start index from hashmap (in this case our previous start index was 0 and new start index which we calculated a just before this step is 1) since they are no longer in our new window, so we remove 'a' from hashmap. Add the current character 'a' to map along with its index to hashmap. Now our diagram looks as shown below: Increment end pointer, s [ end ] = 'b'. Again 'b' is present in map. Update result = max( result , length of substring from index 1 to 3) = max(result , length of substring "bca") = max(3,3) = 3. Delete previous window characters, i.e. delete 'b' from hashmap. Update start = map ['b']+1 = 1 + 1 = 2 and update hashmap, map ['b'] = 4 for current character. Again we increment end pointer, end = 5 which is character 'c' which is a duplicate. We repeat the steps of calculate result, removing previous window characters from map, updating the start pointer and adding the current character to map. result = max( result , length of substring from index 2 to 4) = max( result , length of substring "cab") = max(3,3) = 3. start = map ['c'] + 1 = 2+1 = 3. Remove character 'c':2 from previous window. Add the current character 'c': 5 to our hashmap. Now our diagram looks as below: Increment end pointer again, now end = 6, which is character 'b'. 'b' is also present in our map(we found it earlier at 4 index in our string s). result = max( result , length of substring from index 3 to 5) = max( result , length of substring "abc") = max(3,3) = 3. start = map ['b'] + 1 = 4+1 = 5 and remove all characters before our new start ('c':5, 'a':3 and 'b':4) from our map. Also we update the current character 'b':6 into map. Finally we increment end again, our new end = 7. Again 'b' is present in hashmap. result = max( result , length of substring from index 5 to 6) = max( result , length of substring "cb") = max(3,2) = 3 and start = map['b'] + 1 = 6+1 = 7. Add 'b':7 to map. The end has now reached the end of the string s, so we terminate the loop and return the result. Note : The order in which elements are stored in the map does not matter. Code Language: Go Complexity Analysis Time Complexity: O(n) We check each character in the string only once. Yes we would also have to delete the elements from the hashmap once a duplicate character is found, but this is a constant time operation because at max the map can store only 62 elements in our case before a duplicate is found. Space Complexity: O(1) In the worst case we would have to store all n characters of the string s in hashmap, but this is a constant value which at max can go up to O(62) as explained in solution 1 . That is all for this article, thank you for taking your time to read this. If you have any questions or doubts, please let us know in the comments section below, we will be happy to answer you. If you found this article useful, do not forget to subscribe to our website, your support motivates us to bring out more such articles in future (scroll down to the bottom of the page to find the subscription form). You can explore more such amazing articles from code recipe in our blogs section . ⚡ FREE Premium Access—Only for a Short Time!  ⚡ Love coding? Get expert tutorials, pro tips, and exclusive resources— 100% FREE!  For a limited time, enjoy full access to Code Recipe Membership at no cost. Don’t wait—grab this deal before time runs out! ⏳ Sign up now! Follow us: YouTube , Facebook , Twitter , LinkedIn , Tumblr , Instagram .

Introduction In the previous article we delved into the fascinating world of Go Generics and learnt how to incorporate it in our go programs. In this article we will explore yet another cool feature in Go, the go embed directive. Go has been one of the fastest growing programming languages in the recent years. It is known for its simplicity, robustness and performance. When it comes to features, the Go language is rapidly expanding with new features being added in each new release. The go:embed directive was one such feature which was introduced in go 1.16. This simple yet powerful feature lets you access and manage static assets such as configuration files, certificates and much more like never before! This article will help you with everything you need to know about the go:embed directive in order to leverage its benefits in your day to day work. What is go:embed directive? The first thing we need to know is that, the go:embed is a compiler directive. What this means is, all of the processing that happens when we use the go:embed directive in go, happens at compile time. It is a special directive that is used to include/embed files or directories directly into the compiled binary of our go program. How to use go:embed directive? Using the go embed feature is simple. To use this feature in our go program we simply need to add a comment line `// go:embed` , followed by a space and the path to the file or folder which needs to be embeded. This comment must be added directly above the variable into which we want to our embed files or folders. Both files and folders can be embeded. We can also use patterns or wildcard characters (such as *) along with the file/folder paths. The syntax for using go embed directive is as shown below: Syntax //go:embed < file/folder path or pattern > var variableName embed.FS Patterns will be useful in cases where we have to embed multiple files or folders. For example to embed all the .txt files whose name starts with "config", you need to specify the following: //go:embed config*.txt var variableName embed.FS When the go compiler sees the `// go:embed` comment anywhere in the go code, it interprets it as a special comment. The compiler processes this comment and embeds the files mentioned in the directive directly into the variable that we have defined. This is particularly useful in scenarios where we have to bundle static assets, configuration files, templates, or any other type of data directly into our program binary. Remember all of this happens at compile time. So, you need to have these files in the mentioned path at compile time. Note: Go makes use of the embed package for processing the go embed directive. Example Lets understand this with the help of an example. Lets create a sample go project named sample-project . Create a text file example.txt in the current working directory where the main.go file is located. Your project structure should now look something like this: Now lets add some text to our example.txt file. sample-project/example.txt And then add following code to main.go . sample-project/main.go In the above example, the //go:embed example.txt comment indicates that the file example.txt in the projects' root directory should be embedded into the content variable. content is a variable of type embed.FS from embed package, which is a go core library. Now that example.txt is embeded into the content variable, we can access it using the ReadFile() method (from embed package) as shown in line 12 in the above code. Remember, the embed package needs to be imported (line 4) in order to use this feature. The embed directive and package are available from Go 1.16. So, you will only be able to use this feature if you are using Go 1.16 or later versions. Are you looking to learn new skills and crack interviews in top tech companies? Explore the materials below designed exactly for this purpose: Udemy Video Tutorials - Available at 95% off System Design Interview Complete Guide Cracking The Coding Interview - Most Preferred Book For Coding Interviews Data Structures And Algorithms - A Complete Guide Learn In-Demand Tech Skills And Stay Ahead Of Others Reading files using os or ioutil package vs using go:embed Using Go os or ioutil Libraries When we use the go os or ioutil library to read files ( method 1 , method2 ), we are accessing those files at runtime . The file must be present on the file system when the program is executed. This method is suitable for use cases where our program needs to read files that are dynamic in nature (files whose content keeps changing) or to read files that are not available at the time of compilation (Only available at runtime). Using go:embed Directive The go:embed directive as mentioned earlier is used to embed files or folders at the time of compilation , directly into the compiled binary of the go program. This is the recommended approach for reading files with static content. Summary In summary, the decision on whether to choose approach 1 or approach 2 depends on our use case and we can choose either of them by considering the following main factors: Whether we want to perform read operation at compile time or runtime. Is it a file with frequently changing content or file with static content. Limitations The go:embed directive offers significant advantages, but it is also important for us to understand its limitations: Large Binaries: Since go:embed is a compile time directive it will have an impact on the size of our compiled binary (built using go build command), especially if the embeded files/folders are large. So, it is important that we take this into consideration and embed only those files/folders that our application really needs. Security: Since go:embed is usually used to store static files such as certificates, configurations and these files are directly stored within the binary, it is our responsibility to secure any sensitive information contained within these files. Not for Dynamic Content: As discussed earlier, go:embed directive is used for static files. If your application involves dynamically changing files, go:embed might not be the right choice, in such cases it is better considering the go os or io packages for reading files. Empty folders: Currently embedding empty folders is not supported by this feature. The go embed feature can only be used to embed files in the current working directory or subdirectories under it. It cannot be used to embed files outside the current directory. Conclusion The go:embed directive is a powerful tool that redefines the way developers manage static assets and resources. It simplifies deployment, reduces external dependencies and enables self contained applications. By understanding its benefits, knowing when to use it and recognizing its limitations, we as developers can harness the full potential of the go embed feature. We hope this article has helped you in this aspect and you will be able to make an informed choice the next time you have to use this feature in your go project. That's all we had to cover in this article, thank you for your time. If you have any questions or doubts, please let us know in the comments section below, we will be happy to answer you. If you found this article useful, do not forget to subscribe to Code Recipe , your support motivates us to bring out more such articles and videos in the future. You can explore more such amazing articles from code recipe in our blogs section and by visiting our Youtube channel . Code Recipe Limited Time Offer: Get 100% discount on Code Recipe Membership Plan. Join now and get exclusive access to premium content for free. Hurry! Offer only available for a limited no. of users - Join now . Follow us on social media: Facebook , Twitter , LinkedIn , Tumblr , Instagram .

Introduction Generics is one of the most anticipated and long awaited features in go. Some also argue that it is in some ways a controversial feature since it seems to go against one of the go language's core design principle "simplicity". This however is a topic of discussion for another day, in this article we will go through everything that you need to get up and running with go generics. Also we will delve into some of the finer details and best practices of go generics to get you an advanced level knowledge on this topic. The go generics is finally here! The generics feature was added to the language in the Go release, version 1.18. What is generics in a programming language? Generics is a programming language paradigm that gives us a way to write code that is not tied to any specific type. It gives us the ability to define a generic or common data structure/function that allows us to work with multiple data types (like int, float, string etc). Why generics is needed? Let us understand this with an example. Assume we have a function Add() , that adds two integer types and returns the result as an integer as shown below: The above function works fine as long as our use case is only to add two integer values. Suppose, tomorrow we have a new requirement where in we are required to support float type addition as well, how can we handle this? We cannot use our earlier function because it takes only integer types as input. Prior to Go generics this could be solved in one of the two ways: Defining multiple functions, one for each type. Using an empty interface and type asserting. Approach 1: A natural tendency to solve this is to define a new function that does the exact same thing as our earlier Add() function but with float64 type as shown below. As you can see this is unnecessary duplication of code. It may not seem like a big deal for the above example as our function only involves a simple logic to add two numbers. But in the real world we may have to deal with a much more complicated logic containing hundreds of lines of code and duplicating these complex functions is a waste of time and effort. Also this introduces a maintenance overhead because every time we need to improve or update some piece of code we would have to do this in all the duplicated blocks, which of course is not the best way to handle this. Approach 2: In this approach we use an empty interface that can accept values of any type and in the function body we use type assertion to extract the required type and perform necessary actions. While this looks cleaner than the first approach, it still involves a lot of boilerplate code and is not the most efficient solution to our problem. Scenarios like these is exactly where generics comes into play. Go Generics The generics feature in Go is a major release, according to the official documentation this is the biggest change made to the language since the first open source release. The good news however is that it is fully backward compatible with the code written using earlier versions of Go. In Go a generic type is generally denoted using the notation T , however we are not restricted to using that, we can name it anything. Fig.1 shows a sample Go generic function along with its components. Compared to a normal (non-generic) Go function, you can see there is an additional square bracket between the function name and the parameter list. Also the parameter list contains the generic type parameters (denoted by T ). Go generics can be broadly broken down into 3 components: Type parameters Type sets or type constraints Type inferences Lets discuss each of these components in detail. Want to master coding? Looking to learn new skills and crack interviews? We recommend you to explore these tailor made courses: Udemy Video Tutorials - Available at 95% off System Design Interview Complete Guide Cracking The Coding Interview - Most Preferred Book For Coding Interviews Data Structures And Algorithms - A Complete Guide Learn In-Demand Tech Skills And Stay Ahead Of Others Type Parameters In Fig. 1, the square brackets and the elements inside it together is called a type parameter or type parameter list . Type parameter defines information about the generic type. It contains information like the name of the generic type, data types supported by the generic type etc. A type parameter is defined using the syntax: [T1 constraints , T2 constraints , ... ] Here are a few type parameter definition examples: Example 1 : [T int | int32 | int64 ] Example 2 : [T1 int32 | float64 , T2 string | float64 ] Example 3 : [T constraints.Ordered ] Note: constraints.Ordered is a type of constraint provided by Go and it is defined in the package golang.org/x/exp/constraints , it supports Integer , Float and string types (More details on the constraints.Ordered type can be found here ). Type parameters can be applied to Go functions and Go types (go type keyword). 1. Type Parameter on Go Functions The sample function shown in Fig. 1 is an example of how a type parameter can be applied to a Go function. Let us understand this more clearly by studying how we can redefine our earlier Add() function to support integer and float types using Go generics. As you can see we can convert our non-generic Add() function to a generic Add() function by adding a type parameter definition after the function name and replacing the specific types ( int , float64 ) with generic type T . This generic Add() function can be called using both integer and float data types, there is no need to redefine or duplicate the function body like we saw earlier. How to call a generic function? Calling a generic function involves two steps: 1. Instantiation 2. Function call Instantiation In this step we tell the compiler what specific type we want to pass into our generic type. The compiler then checks whether this data type satisfies the type parameter constraints. For example the constraints, constraints.Integer and constraints.Float types used in our above generic Add() function, supports Integer, Float data types. If anything other than these types is used during instantiation, it throws a compile time error. The syntax for instantiation is: funcVariable := function_name[data_type] For example we can instantiate our above generic add function with int data type as shown below: AddFunc := Add[int] For float64 type we need to use float64 inside the square brackets as shown below: AddFunc := Add[float64] Function call The instantiation step returns a func type variable. In this step we call the generic function using this func type variable that we obtained during the instantiation step as shown below: result := AddFunc(10, 20) So to summarize, in order to call a generic function we need to first instantiate and then call the function as shown below: AddFunc := Add[int] result := AddFunc(10, 20) Go also supports a simplified syntax where we can combine the instantiation step and function call step into a single line of code: result := function_name[data_type](argument_list) This means we can call our Add() function using a single line of code as shown below: result := Add[int](10, 20) 2. Type Parameter on Go Types Type parameters can also be applied to types defined using the Go type keyword. Let us understand this again by taking the addition example: Let us define a custom add type (a generic type) using type parameters. The custom add type struct should have two fields for storing the numbers to be added. The Add() function should add the values in these two fields and return the result. In above example we have defined a custom struct type CustomAddType that has two fields num1 and num2 . Both num1 and num2 are of type T (generic type). The type parameter is defined after the type name inside square brackets. We have defined an Add() method for this generic struct type. This method adds the generic types num1 and num2 and returns the result. To call this add method we need to instantiate the CustomAddType type first and then call the Add() method on it as shown below: Since num1 and num2 are generic types we can pass both int and float (defined by type constraints) values to it. Type Sets In the previous section we have learnt that type parameters can be defined with the syntax: [T constraints ] The "constraints" part in the type parameter syntax is what we refer to as the type sets or type constraints . In simple words type sets define the range of types or set of types a generic type T supports. The benefit of using type constraint is that it allows us to define a set of supported types. This approach is unlike the generics implementation in other languages like C#, C++ where type parameters are completely type agnostic. The type constraint way of implementation is intentionally added to Go generics to reduce misuse. Type Sets are Interfaces An important thing to note is, everything that we define as a type set is an interface ! Yes that's right, every type set is an interface. For example the constraints.Ordered type set we saw earlier, is an interface defined in constraints package. The definition of constraints.Ordered is as shown below: Similarly, constraints.Integer and constraints.Float types that we used in our generic Add() function are also interfaces. New Interface Syntax If you have been using Go for a while now, the interface syntax you see above might look a bit weird to you. Interfaces in Go used to have only methods and other interfaces embedded in them, but this is a little different. That's because, this is a new syntax introduced in Go 1.18 for use in generics. Now we are allowed to have types inside interfaces as well. We are also allowed to specify multiple types inside interfaces separated by the union operator as shown in the example below: The MyInteger interface shown above defines a new type set with int , int8 and int16 as possible types. The | symbol denotes a union, meaning the MyInteger interface is a union of int , int8 and int16 types. Similarly we can have interfaces with other types like string , float64 etc. We can also embed interfaces/type sets inside other interfaces/type sets. Example, In fact if you observe carefully, constraints.Ordered itself is a union of Integer and Float type sets which are in turn interfaces. Tilde Operator If you look at the constraints.Ordered type definition there is a ~ symbol before the string type. A tilde before a data type means the following things: Allow all values corresponding to that data type. Allow all values whose underlying type is the current data type. For example a ~string means 1. Allow all values of string type. 2. Allow all values whose underlying type is string (Ex: type customString string). Custom Type As Type Constraint We are also allowed to define our own custom constraints as shown in example below: type CustomConstraint interface { int | string } We can use these custom type sets in our type parameter declaration as shown below: [ T CustomConstraint ] Interface Literal As Type Constraint We can also use interface literals as type sets. For example, [T interface{ int | int8 | int16 }] Go allows us to simplify the interface literal syntax, we are allowed to skip the interface{} part from the above syntax: [T int | int8 | int16] If you go back to Fig.1, this is the reason why we where able to specify [T int | int32 | float64] without the interface{} . Inbuilt/Pre-Defined Type Constraints You might aware of the empty interface usage in Go. An empty interface i.e. interface{} in general means that it satisfies all types (since it has no methods inside it). Similarly in the context of type parameters, an empty interface represents a generic type which can be instantiated using any type. For example, the generic add function given below can take any type like int , int32 , float32 , string etc. Go 1.18 has introduced a new keyword called any to represent an empty interface, interface{}. Using this keyword, the above add function can be equivalently written as: In addition to any , Go provides another pre-defined type constraint comparable . comparable denotes the set of all non-interface types that are comparable . Specifically, a type T implements comparable if: T is not an interface type and T supports the operations == and != or T is an interface type and each type in T 's type set implements comparable. comparable can also be embedded in other constraints since it is a constraint. That's it for the type sets section. Yes it can be quite overwhelming at first, given so many syntaxes and shorthands, but you will get used to it as you practice it more and more. Type Inference Type inference in the context of Go generics means how the compiler interprets the types that are being passed to a generic type. We can broadly classify type inference in go generics into two categories: Function argument type inference Constraint type inference Let us discuss each of them in detail. Function argument type inference We have seen in the previous sections how we can instantiate and call a generic function. Say for example if we have a generic function for multiplying two numbers: To instantiate and call the above generic function, we would write the following lines of code: multiply := Multiply[int] multiply(10,20) This is one way of doing it. As we learnt the syntax can be simplified by combining the two steps into a single step: Multiply[int](10,20) While this is shorter than the first syntax and easier to read, it is still cumbersome. Go simplifies this further by allowing us to skip the type argument instantiation part as shown below: Multiply(10,20) As you can see, with this syntax, we do not have to specify [int] while calling our generic multiply function and with this the syntax now is exactly same as a normal function call. How this works is, when you call a generic function this way the compiler internally infers the type from the arguments provided in the function call. In our example above, the compiler sees that the arguments (10,20) is passed to the function, so it infers the type to be int and substitutes this type for num1 and num2 parameters in the generic function. This way of inferring the type by the compiler in a generic function call by looking at its arguments is called function argument type inference . The limitation with this approach however is that, if we need a specific type, say for example int32, we will still have to explicitly mention it using the earlier syntax itself. But for other cases this helps us further simplify the syntax and improve the code readability. One thing to remember about function argument type inference is that it only works for type parameters that are used in the function parameters . This does not apply for type parameters used only in function results or type parameters used only in the function body. For example, it does not apply to functions like, that only uses T for result. Constraint type inference Another kind of type inference that is supported by Go generics is the constraint type inference. Look the sample generic function above, you can see the type of the parameter U is defined as ~[]T and the type of parameter T is any. In such cases the compiler infers the type of the parameter U using the type of the parameter T when GenericFunc() is called. For example lets say we call this function like: The compiler now see that the type U is a slice of T and the type of the parameter T is int . Therefore it can determine from the call the type of the parameter U is of type []int . This way of inferring the the types is referred to as constraint type inference in Go generics. Go Generics Best Practices 1. Use ~ in type set definition for predefined types When creating a constraint, that has builtin types and methods in the interface, ensure the constraint specifies any builtin type using the ~ token. If ~ is missing for any of the builtin types, the constraint can never be satisfied since Go builtin types cannot not have methods. For example lets define a constraint called SampleConstraint that has a String() method in the interface: Let us write a generic function that uses SampleConstraint : Now let us define a type called TestType that implements SampleConstraint : When you run this code using: you will see the following error: ./prog.go:15:10: TestType does not implement MyConstraint (possibly missing ~ for string in constraint MyConstraint) Go build failed. To fix this we need to add a ~ before the string data type as show below: 2. Type parameter constraints should be narrow and explicit This means when we write a new generic function, when we know what the expected types are, it is better to explicitly specify the type constraints that we expect our generic function to be called with like int, int32, float32 etc. rather than using "any" or interface{} as type constraints. This would allows us to seamlessly add new functionality to our generic function in future without breaking the existing code or having backward compatibility issues. For example, let say we write a new generic function to display the price of a product and we know for a fact that the type of price we get as input is expected to be of type int64 or float64. But we still go ahead and use "any" as the type constraint: Now suppose we get a requirement tomorrow to add tax to the price before displaying it, we need to make the following change to our code: But when we try to compile the code we get the following error: ./prog.go:31:18: cannot convert price (variable of type T constrained by any) to type int Go build failed. Instead if we had explicitly constrained our type parameter to int64 or float64 as shown below, our function would have worked as expected. This is one of many scenarios where having a generic function with explicit type constraints helps. The other thing is, giving a broader range of values (more than what is needed) gives scope for unexpected errors. This means that our implementation is expected to ensure that we have written all the code needed to handle failure cases for all the types specified by our type constraints. When Not To Use Generics Generics is a great tool for writing reusable code, however, it does not mean that it is always the best tool. Majority of situations that we encounter on a daily basis do NOT require generics. As a guideline if you see lots of duplicated code blocks, you could consider replacing it with generic code. If the code you are writing can be constrained down to a couple of types, then perhaps it is better to use interfaces instead. Summary Generics is a big feature introduced in go 1.18 and is an important one. Compared to other languages the Go generics implementation is much more intuitive and easy to read. Go generics implementation is designed in such a way that type parameters are not type agnostic, the constraint based implementation that Go follows is a result of years of experimentation in order of to find the right approach by the Go team. The main aim of this approach is to prevent confusion and misuse of generic types. However, Go generics is still a new feature and it has a long way to go before it could confidently use in production. We are sure, there will be improvements and new code added in the coming days to enhance the stability of the existing version. We will make sure to keep this article updated in case of any new updates or announcements. That is all for this article, thank you for taking your time to read this. If you have any questions or doubts, please let us know in the comments section below, we will be happy to answer you. If you found this article useful, do not forget to subscribe to Code Recipe , your support motivates us to bring out more such articles in future (scroll down to the bottom of the page to find the subscription form). You can explore more such amazing articles from code recipe in our blogs section . Code Recipe Limited Time Offer: Get 100% discount on Code Recipe Membership Plan. Join now and get exclusive access to premium content for free. Hurry! Offer only available for a limited time - Join now . Follow us on social media: Facebook , Twitter , Linkedin , Tumblr , Instagram .

Hello Code Recipian! Ready to push your coding prowess to the next level? Today's question: Subarray Sums Divisible by K —a great challenge to put your coding skills to work! This challenge is part of our   LeetCode problem solutions series, so don't forget to check out more once you've cracked this one. Let's jump in and solve this together! Problem Statement: 974. Subarray Sums Divisible by K Given an 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 Justification: There are 7 subarrays whose sum is 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 = [7], k = 2 Output: 0 Constraints 1 <= nums.length <= 3 * 10^4 -10^4 <= nums[i] <= 10^4 2 <= k <= 10^4 Solution: 974. Subarray Sums Divisible by K Before attempting this problem, make sure you have already solved the Subarray Sum Equals K problem. If you haven't, please do so first and then return to this one. This problem is a more advanced variation, and without the basics set, you will have a hard time understanding this. Brute force approach: As discussed in Subarray Sum Equals K , a simple and straight forward way to solve this problem is by using the brute force approach. This involves employing two nested loops to generate all possible subarrays for the given nums array and counting those whose sum equals k . However, due to the use of nested loops, this solution has a time complexity of O(n ² ) , making it inefficient. Sliding window technique cannot be applied here, for the same reasons outlined in Subarray Sum Equals K . Prefix Sum Approach: We will be using the prefix sum approach here as well, as it provides an efficient way to solve this problem. If you recall, the brute force method generates and counts subarrays that start at a particular index. However, the prefix sum approach takes the opposite perspective—it counts the subarrays that end at a particular index. If you think about it, iterating from left to right and counting subarrays starting at a given index can be challenging since we don't know in advance how many subarrays will satisfy the condition. However, if we instead consider how many subarrays end at a particular index (i.e., the current index), the problem becomes much simpler because we have already processed the elements to the left. If this seems unclear, don't worry—it will make sense once we walk through an example. Consider the given input: nums = [4, 5, 0, -2, -3, 1]  and k = 5 Let's start with the first element, 4 (at index 0 ). The only possible subarray is [4] . Check if its sum is divisible by k : 4 % 5 = 4 (not divisible). 💡 Note: A number x is divisible by y , only if x % y = 0 . Now, moving to the next element, 5 (at index 1 ), the possible subarrays ending here are: [4, 5]  → Sum = 9 , and 9 % 5 = 4  (not divisible). [5]  → Sum = 5 , and 5 % 5 = 0 (divisible ✅). Since [5]  is divisible by k , we add 1  to our result. Continuing to index 2  (element 0 ), the possible subarrays ending here are: [4, 5, 0]  → Sum = 9 , and 9 % 5 = 4  (not divisible). 5, 0]  → Sum = 5 , and 5 % 5 = 0  (divisible ✅). [0]  → Sum = 0 , and 0 % 5 = 0  (divisible ✅). Since two subarrays satisfy the condition, we add 2  more to our result. Identifying a Pattern: Now, let's analyze the pattern behind this approach. At index 2 , the prefix sum  is 9 , and 9 % 5 = 4 . For a subarray ending at this index to be divisible by k, there must be a previous subarray  whose remainder is also 4 . The diagram below illustrates how we determine if the subarray [5, 0]  (ending at index 2) is divisible by k=5 : Now let's analyze the above calculation and build a pattern out of it. If you notice, at a particular index, as an example let's consider index 2, the prefix sum at index 2 is equal to 9, and 9%5 = 4, so in order for a subarray ending at this index to be divisible by k , i.e. to get a remainder 0, there must be a subarray before this index whose remainder is equal to 4 . Diagram showing the prefix sum and remainder calculations for subarray [5, 0] Diagram showing the prefix sum and remainder calculations for subarray [0] From the above analysis we can conclude that a subarray ending at a particular index is divisible by k if: currentSum % k - previouslySeenSum % k = subarraySum % k = 0 or currentSum % k = previouslySeenSum % k Storing Previously Seen Remainders: This algorithm keeps track of remainders encountered in previous iterations, along with their frequencies. To enable quick lookups and avoid quadratic time complexity, these remainders are stored in a hashmap, seenRemainders . Additionally, the hashmap is initialized with {0:1} to handle cases where the prefix sum exactly divisible by k upon first occurrence. Without this initialization, such cases would be missed, leading to incorrect results. Normalizing Negative Remainders: The algorithm relies on tracking prefix sum remainders  to count subarrays whose sum is divisible by k . However, if the remainders are negative and not normalized , the approach breaks down. Here's why: Consider nums = [-3, -7]  and k = 5 . At index 1, currentSum % k → -10 % 5 = 0 . And previouslySeenSum % k  → -3 . Since currentSum % k  does not match  previouslySeenSum % k the algorithm incorrectly concludes that there is no valid subarray, when in reality, the subarray [-3, -7] is divisible by k . We can normalize negative remainders using the formula: remainder := ((prefixSum % k) + k) % k This formula ensures all remainders fall within the valid range [0, k-1] ensuring consistency in hashmap lookups. Now let's revisit the previous example using this formula: At index 1, currentSum % k → ( (-10 % 5) + 5) % 5 = 0 . And previouslySeenSum % k  → ( (-3 % 5) + 5) % 5 = 2 . Since the seenRemainders hashmap is initialized with {0:1} , the algorithm correctly identifies a valid subarray and returns a count of 1. Let's now discuss how to implement this approach. Algorithm Below is a step-by-step breakdown of how the algorithm works: Initialization: Create a hashmap seenRemainders , to track prefix sum remainders encountered in previous iterations. Initialize seenRemainders with {0:1} to handle edge cases where the current remainder is exactly k . Define two variables: prefixSum → Stores the cumulative sum. subarrayCount → Stores the final count of valid subarrays. Count subarrays divisible by k: Iterate through the nums array and perform the following steps for each element: Update the prefixSum by adding the current number. Normalize the remainder to handle negative values using the formula: remainder := ((prefixSum % k) + k) % k Check if the remainder exists in seenRemainders hashmap: If it exists, add its frequency to subarrayCount . If not, continue to next step. Increment the frequency of the current remainder in seenRemainders . Repeat steps a to d for every number in nums . Return the final result: Return subarrayCount as the final count of subarrays divisible by k . Want to master coding? Looking to upskill and crack interviews? We suggest you check out these specially designed courses: Artificial Intelligence A-Z 2025: Build 7 AI + LLM & ChatGPT Udemy Video Tutorials - Available at 95% off System Design Interview Complete Guide Data Structures And Algorithms - A Complete Guide   Learn In-Demand Tech Skills And Stay Ahead Of Others Simulation Here’s a visual representation of how the algorithm works: Code Go Solution Python Solution Java Solution JavaScript Solution TypeScript Solution C++ Solution C# Solution C Solution PHP Solution Kotlin Solution Swift Solution Ruby Solution Scala Solution Rust Solution Dart Solution Racket Solution Complexity Analysis Time Complexity The algorithm processes the nums array in a single pass, resulting in a time complexity of O(n) . Space Complexity The algorithm uses a hashmap seenRemainders to store prefix sum remainders. In the worst case, where all remainders are unique, that hashmap will store upto n elements. Therefore, the space complexity is also O(n) . Want to master the Prefix Sum pattern?  Take your skills to the next level with these must-read articles: 930. Binary Subarrays With Sum 560. Subarray Sum Equals K Coding Patterns – Prefix Sum Pattern 1991. Find the Middle Index in Array Left and Right Sum Differences Dive in now and take your coding game to the next level! ⚡ FREE Premium Access—Only for a Short Time!  ⚡ Love coding? Get expert tutorials, pro tips, and exclusive resources— 100% FREE!  For a limited time, enjoy full access to Code Recipe Membership at no cost. Don’t wait—grab this deal before time runs out! ⏳ Sign up now!

Hello Code Recipian! Ready for another LeetCode challenge? Today, let's tackle another LeetCode problem that uses the prefix sum pattern, 560. Subarray Sum Equals K . This article is part of our exciting series LeetCode problem solutions —be sure to explore the other problems in the series once you’ve mastered this one! Alright, let’s dive into today’s problem! Problem Statement: 560. Subarray Sum Equals K Given an integer array nums and an integer k , return the total number of subarrays in nums whose sum is equal to k . Example 1 Input:  nums = [1, 1, 1], k = 2 Output:  2 Example 2 Input:  nums = [1, 0, 1, 2, 1, 0, 4, 1, 3], k = 4 Output:  8 Constraints 1 <= nums.length <= 2 * 10^4 -1000 <= nums[i] <= 1000 -10^7 <= k <= 10^7 Solution: 560. Subarray Sum Equals K Let's dissect the problem statement. For a given array, a subarray is a chunk in this array where all the elements are in a continuous sequence—no skipping allowed! Think of it like highlighting a part of a sentence, you cant jump over words. For example, consider the below array: Subarrays for the given array are: The problem statement asks us to count all such subarrays in nums whose sum is equal to k . A straight forward approach to solve this problem is to use two nested loops to generate all subarrays for nums and count the matching subarrays with sum k . But, because of nested loops, the time complexity of this solution is O(n^2) , which for sure is not an efficient solution. Can sliding window technique be used to solve this? Usually when we see subarray problems, one approach that naturally comes to mind is the sliding window technique. A good way to evaluate if sliding window technique can be applied for a subarray problem is to analyze the problem closely. If the problem statement has loose or flexible constraints like "subarrays with sum less than k", "smallest subarray with a greater sum" etc. this is where sliding window can be a great fit. For subarray problem with stricter constraints like the one given in this question "subarray sum equals k", sliding window pattern cannot be applied because they violate the window expansion/contraction constraints. Consider the below example, In sliding window technique, we update the result both in expansion and contraction phase. We keep expanding the window as long as sum<=k and contract it when sum>k . As you can see from the above diagram, for input nums =[1, 0, 1, 0, 1] and k=4 , the expected output=4 , but we get 3. This is because sliding window misses the last subarray, as shown in below diagram (highlighted in red): This is exactly why the sliding window approach won’t work here—it would overlook some subarrays and result in an incorrect outcome. Prefix Sum Approach Consider the below input array and k=4 : Assume we are iterating through the array and we have reached the 4th index i.e. element 1. At this point in order to get subarray with sum=4, there are two possibilities [0, 1, 2, 1] and [1, 2, 1], shown by the cells highlighted in green in the below diagram: Let's analyze how we can arrive at this result. If you observe carefully, in order to get these two subarrays, i.e. in order to get sum k=4 , we need to subtract the sum of elements not part of the subarray from the sum of all elements until the current element. A closer examination reveals that nonSubarraySum , currentSum are nothing but prefix sums for the respective indices. Note: If you are new to prefix sum coding pattern, we recommend you go through this article on prefix sum Coding Patterns - Prefix Sum Pattern , in order to understand this solution better. Now that we understand how to find a subarray with sum k , let’s move on to figuring out how to count all such subarrays. Referring back to the same example, at index 4 , we know two subarrays with sum=4 are possible. We identified these subarrays by subtracting the prefix sums: And if you notice at at index 4, where prefixSum[4]=5 we can get sum=4 only when subtracted prefix sum is equal to 1 i.e. prefixSum[0] == prefixSum[1] = 1 . We got 2 subarrays at index 4 since we had 2 prefix sums with value equal to 1. From the above analysis, we can deduce that the number of possible subarrays at a particular index is determined by the count of previous prefix sums that, when subtracted, result in the desired difference of k . By applying this logic to every index in nums array, we can calculate the total count of subarrays with a sum equal to k . And final thing to consider: since we need quick access to previously seen prefix sums while iterating through the nums array, we’ll store them in a hashmap. This hashmap will also track the frequency (count) of each prefix sum, allowing us to solve the problem efficiently. Algorithm Here’s a quick overview of how the algorithm works and how it can be implemented: Initialization: Initialize a hashmap seenPrefixSum to keep track of previously encountered prefix sums and their frequencies. It takes prefix sum as key and the corresponding count as value. Add an initial entry {0:1} to the hashmap. This ensures edge cases are handled, such as when the current prefix sum equals k . Create an integer variable currPrefixSum and set it to 0. This will store the running prefix sum as we iterate through the nums array. Finally, initialize a variable count to store the result—the total number of subarrays with a sum equal to k . Count subarrays with sum k: Iterate through the nums array from start to finish. In each iteration perform the following steps: Add the current element to currPrefixSum to update the running prefix sum. Check if currPrefixSum - k exists in the seenPrefixSum hashmap. If yes, add the frequency of currPrefixSum - k from the hashmap to count . If no, proceed to the next step. Add the current currPrefixSum to the hashmap(or update its frequency if it already exists). Continue iterating through the array. Return the final result: Once the iteration through the nums array is complete, return the value of count as the final result. Want to master coding? Looking to upskill and crack interviews? We suggest you check out these specially designed courses: Artificial Intelligence A-Z 2025: Build 7 AI + LLM & ChatGPT Udemy Video Tutorials - Available at 95% off System Design Interview Complete Guide Data Structures And Algorithms - A Complete Guide   Learn In-Demand Tech Skills And Stay Ahead Of Others Simulation Code Go Solution Python Solution Java Solution JavaScript Solution TypeScript Solution C++ Solution C# Solution C Solution PHP Solution Kotlin Solution Swift Solution Ruby Solution Scala Solution Rust Solution Dart Solution Racket Solution Complexity Analysis Time Complexity Time complexity of this algorithm is O(n) as we have to iterate through the array once in order to find the result. Space Complexity Space complexity is O(n) as we store prefix sums in the seenPrefixSum hashmap, and in the worst case when all prefix sums are unique, we will end up storing n prefix sums in hashmap. Curious to learn more on prefix sum pattern? Checkout our other articles on prefix sum pattern: Coding Patterns - Prefix Sum Pattern 1991. Find the Middle Index in Array Code Recipe Limited Time Offer:  For a limited time enjoy 100% discount on the Code Recipe Membership Plan. Sign up now and get access to exclusive premium content for free. Hurry—offer expiring soon - Join now .

Hello Code Recipian! Ready to put your coding skills to the test? Today, let's solve LeetCode problem 2574. Left and Right Sum Differences . Oh, and if you’re on a roll, don’t stop here! This article is part of our epic LeetCode problem solutions series, so be sure to check out the others once you’ve cracked this one. Alright, let’s dive in and break this problem down! 🔥 Problem Statement: 2574. Left and Right Sum Differences Given an integer array nums , return an integer array result such that: result.length == nums.length . result[i] = |leftSum[i] - rightSum[i]| . Where: leftSum[i] is the sum of elements to the left of index i in nums . If there is no such element, leftSum[i] = 0 . rightSum[i]  is the sum of elements to the right of index i  in nums . If there is no such element, rightSum[i] = 0 . Example 1 Input: nums = [10, 4, 8, 3] Output: [15, 1, 11, 22] Justification: leftSum = [0, 10, 14, 22] and rightSum = [15, 11, 3, 0]. Hence, result = [ |0 - 15|, |10 - 11|, |14 - 3|, |22 - 0| ] = [15, 1, 11, 22]. Example 2 Input:  nums = [2, 5, 1, 6, 1] Output:  [13, 6, 0, 7, 14] Constraints 1 <= nums.length <= 1000 1 <= nums[i] <= 105 Solution: 2574. Left and Right Sum Differences Brute Force Approach: A naïve way to solve this problem is to use the brute force approach. The brute force approach involves computing leftSum[i] and rightSum[i] separately for each index i in nums array and then calculating the difference between them. However, this results in an O(n ² ) time complexity, making it impractical for large inputs. Prefix and Suffix Sum Array Solution: In this approach, instead of re-calculating left and right sum for each index, we store them in leftSum and rightSum arrays. As we traverse through the nums array, we can retrieve the corresponding left and right sums from these arrays to compute the result. While this solution has a time complexity of O(n) , it also requires O(n) space due to the use of two additional arrays. Optimized Prefix Sum Solution: Rather than storing the left and right sums in separate arrays, we can maintain their running sums using two variables leftSum and rightSum . This approach eliminates the need for extra space, optimizing space complexity. The diagram below illustrates how the left and right sums are calculated at a specific index (using index 3 as a reference): Let's see how this algorithm works in detail. Algorithm Calculate total sum: Initialize an integer variable rightSum . Iterate through the nums array and compute the total sum of all elements, store this in rightSum variable. Compute the result: Initialize an integer variable leftSum to keep track of the running sum of elements to the left of the current element. Initially leftSum is set to 0 . Create an array result of size n (length of nums ) to store the computed differences. Iterate through the nums array from start to finish. In each iteration perform the following steps: Update right sum by subtracting the current element from rightSum : rightSum = rightSum - nums[i] Compute the absolute difference between leftSum and rightSum and store it in result[i] . Add the current element to leftSum for the next iteration: leftSum = leftSum + nums[i] Repeat these steps for all elements in nums . Return the result: Once all elements have been processed, return the result array containing the left and right sum differences. Want to master coding? Looking to upskill and crack interviews? We suggest you check out these specially designed courses: Artificial Intelligence A-Z 2025: Build 7 AI + LLM & ChatGPT Udemy Video Tutorials - Available at 95% off System Design Interview Complete Guide Data Structures And Algorithms - A Complete Guide   Learn In-Demand Tech Skills And Stay Ahead Of Others Simulation Code Go Solution Python Solution Java Solution JavaScript Solution TypeScript Solution C++ Solution C# Solution C Solution PHP Solution Kotlin Solution Swift Solution Ruby Solution Scala Solution Rust Solution Dart Solution Racket Solution Complexity Analysis Time Complexity Calculating total sum: The algorithm iterates through the nums array once to calculate rightSum . This takes O(n) time. Populating the result: Calculating the difference between leftSum and rightSum and for each element and stroing it in result also requires O(n) time. populating it in result also takes O(n) time since we need to iterate through each element in nums . Since both steps run in O(n) time, the overall time complexity of this solution is: O(n) + O(n) = O(n) . Space Complexity The space complexity is O(1) since no extra space is used that depends on the input size, apart from the output array. Want to master the Prefix Sum pattern? Dive deeper with these must-read articles: 930. Binary Subarrays With Sum 560. Subarray Sum Equals K Coding Patterns – Prefix Sum Pattern 1991. Find the Middle Index in Array Start exploring now and level up your problem-solving skills! ⚡ FREE Premium Access—Only for a Short Time!  ⚡ Love coding? Get expert tutorials, pro tips, and exclusive resources— 100% FREE!  For a limited time, enjoy full access to Code Recipe Membership at no cost. Don’t wait—grab this deal before time runs out! ⏳ Sign up now!

Hello Code Recipian! Today, we'll solve another interesting LeetCode question 930. Binary Subarrays With Sum . This problem has featured in coding interviews at top companies such as Google, Uber and C3 AI. This article is one of many in our LeetCode problem solutions series—be sure to explore them once you have nailed this one! Alright, let’s jump straight into the problem statement now. Problem Statement: 930. Binary Subarrays With Sum Given a binary array nums and an integer goal , return the number of subarrays with a sum equal to goal . A subarray is a contiguous part of the given array. Example 1 Input:  nums = [1, 0, 1, 0, 1], goal = 2 Output:  4 Explanation:  The nums array has 4 subarrays with sum equal to goal : [ 1, 0, 1 , 0, 1] [ 1, 0, 1, 0 , 1] [1, 0, 1, 0, 1 ] [1, 0, 1, 0, 1 ] Example 2 Input:  nums = [1, 1, 1, 1, 0, 0], goal = 3 Output:  4 Constraints 1 <= nums.length <= 3 * 10^4 nums[i] is either 0 or 1 . 0 <= goal <= nums.length Solution: 930. Binary Subarrays With Sum Brute Force Approach: A straight forward way to solve this problem is by using the brute force approach. Use two nested loops to iterate through all possible subarrays of the given nums array and count the subarrays whose sum equals goal . However, since this approach relies on nested loops, it has a time complexity of O(n ² ) , making it highly inefficient. Normal Sliding Window Technique: The standard sliding window technique cannot be applied directly to this problem due to certain constraints in window expansion and contraction, as well as the presence of negative numbers. We have discussed these limitations in 560. Subarray Sum Equals K . To understand this in detail, we recommend going through that article. Prefix Sum Approach: This problem can be efficiently solved in linear time using the exact prefix sum technique discussed in 560. Subarray Sum Equals K . Although this is a valid and commonly accepted solution in interviews, since we are already familiar with it, we will explore a more innovative and insightful solution! Modified Sliding Window Approach: We know that the given array consists of only 0s, 1s and does not contain negative numbers . We can use this fact to our advantage, and apply the modified sliding window to solve this problem in linear time. In this approach, we first use the sliding window to calculate the count of subarrays with a sum at most equal to the goal . Then, we apply the sliding window again to calculate the count of subarrays with a sum at most equal to goal - 1 . Using these two counts, we can determine the number of subarrays with a sum exactly equal to the goal using the formula: Count of subarrays with sum equal to goal = Count of subarrays with sum at most goal - Count of subarrays with sum at most (goal - 1) The intuition behind this approach is that, when we subtract count of subarrays with sum at-most goal - 1 from count of subarrays with sum at most goal, all the common subarrays from both cancel each other out, and we will be left with only the subarrays whose sum is equal to goal. Note: This approach only works if the given input consists of non-negative numbers. Let's understand this with an example. Consider the given array nums= [1, 0, 1, 0, 1] and goal = 2 . Below is the list of subarrays for sum at most 2 and at most 1 at each index in nums : By subtracting these two counts, the common subarrays cancel out, leaving only the count of subarrays whose sum equals 2, as illustrated in the diagram below. Algorithm The solution is implemented in two parts. Part 1: Define the function countSubarraySumAtMostK() , which calculates the number of subarrays with a sum at most k . Part 2: Call countSubarraySumAtMostK() twice: First, to count subarrays with a sum at most goal . Second, to count subarrays with a sum at most goal - 1 . The final result is obtained by subtracting the second count from the first. Implementing countSubarraySumAtMostK() : Initialization: Initialize four variables: start , end , sum and count . start , end track the boundaries of the sliding window. Both start at index 0 . sum keeps track of the current window's sum while we iterate through the nums array. count is used to store result, total number of valid subarrays with sum equal to goal. Counting subarrays with sum at most K: Iterate trough the nums array from start to finish. In each iteration perform the following steps: Expand the window by adding the current element to sum . If sum exceeds k , shrink the window by removing elements from start until sum becomes equal to k . Since sum is now at most k , count all valid subarrays ending at end . This count is given by the formula: count = end - start + 1 . Returning the final count: Once the iteration through nums array is complete, return the value of count as final result. How does the formula end - start + 1 for counting subarrays work? All subarrays that end at end and start anywhere between start and end . These subarrays are valid because their sum is always ≤ goal , as we ensure this by expanding and shrinking the window before applying the formula. The number of such subarrays at index end is end - start + 1 . The formula works because, the subarrays that satisfy this condition are [nums[start]], [nums[start], nums[start+1]], ..., [nums[start],...,nums[end]] . Their count is simply end - start + 1 . Since there are exactly ( end - start + 1 ) such subarrays, adding this value to count ensures we correctly count all subarrays ending at end that have a sum ≤ goal . Want to master coding? Looking to upskill and crack interviews? We suggest you check out these specially designed courses: Artificial Intelligence A-Z 2025: Build 7 AI + LLM & ChatGPT Udemy Video Tutorials - Available at 95% off System Design Interview Complete Guide Data Structures And Algorithms - A Complete Guide   Learn In-Demand Tech Skills And Stay Ahead Of Others Simulation The following diagram visually illustrates how the algorithm works: Code Go Solution Python Solution Java Solution JavaScript Solution TypeScript Solution C++ Solution C# Solution C Solution PHP Solution Kotlin Solution Swift Solution Ruby Solution Scala Solution Rust Solution Dart Solution Racket Solution Complexity Analysis Time Complexity Helper function countSubarraySumAtMostK(): The helper function processes each element in nums at most twice —once when the end pointer expands the window and once when the start pointer shrinks it . As a result, the time complexity is O(n) + O(n) = O(n) . Main function numSubarraysWithSum(): The main function invokes the helper function twice: once for subarray sum at most goal and once for subarray sum at most goal - 1 . Each call takes O(n) time, as explained above. Thus, the overall time complexity of the solution is O(n)  + O(n)  = O(n) . Space Complexity The algorithm uses a constant amount of extra space for variables like start , sum , end etc., regardless of the input size. Therefore space complexity of this algorithm is O(1) . Want to learn more about the prefix sum pattern? Explore our other articles on this topic: Coding Patterns - Prefix Sum Pattern 1991. Find the Middle Index in Array 560. Subarray Sum Equals K 100% FREE for a Limited Time! :  Enjoy Expert Tutorials, Pro Tips, and Exclusive Resources at ZERO Cost! For a limited time enjoy 100% discount on the Code Recipe Membership Plan. Sign up now and get access to exclusive premium content for free. Hurry— claim your FREE access before the timer runs out! - Claim now .

Hello Code Recipian, we come back! We are launching a new series on Coding Patterns and this article marks the first in the series. What are Coding Patterns? A coding pattern refers to a common approach or technique used to solve a specific category of coding questions. A strong understanding of coding patterns and ability to recognize patterns quickly, can make solving coding questions a lot more easier, particularly in coding interviews. Prefix Sum Pattern Prefix sum is an efficient and powerful technique, often useful in coding interviews and competitive coding. A prefix sum is the combined sum of all elements till the current index. Example, for array arr = [1, 2, 3, 4], Prefix sum at index 0 = 1 Prefix sum at index 1 = 1 + 2 = 3 Prefix sum at index 2 = 1 + 2 + 3 = 6 Prefix sum at index 3 = 1 + 2 + 3 + 4 = 10 For a given array arr , a prefix sum array is a new array formed by summing up all the elements upto a specific index, and this is done for every index in arr . For example, consider the array arr = [1, 2, 3, 4]. The prefix sum array for arr is prefixSum = [1, 3, 6, 10]. Here each element in prefixSum array is a sum of all elements from the beginning of arr array to the current index. How is Prefix Sum Useful? Prefix sum provides an efficient way preprocess and query cumulative information about arrays and sequences. Once the prefix sum array is formed (takes O(n) time), it allows us to solve a variety of problems in linear time which might otherwise require complex or inefficient solutions. Range Sum Query using Prefix Sum Let us consider one such application of prefix sum pattern, "Finding the Range Sum". Having a pre-computed prefix sum array allows us to get the sum of a range of elements (sum of any subarray) in the given array in O(1) time. Let's see how we can do this. If start is the starting index of a range and end is the ending index. The range sum of arr from start to end can be calculated using the formula: Range Sum(start, end) = prefixSum[end] - prefixSum[start - 1] If the range starts from first element, i.e. if start = 0 then, Range Sum(0, end) = prefixSum[end] Algorithm: Range Sum Query using Prefix Sum Below is a detailed explanation for the working of the algorithm: Initialization: Consider arr is the given input array having size n . Create a new array prefixSum of same size n . Initially the prefixSum array is empty (or initialized default values). Construct prefix sum array: Assign the first element of arr to prefixSum[0] (since there are no elements before index 0 to calculate prefix sum). Iterate through the given input array arr from index 1 to n-1 . In each iteration calculate the prefix sum at the current index. The prefix sum at the current index i can be calculated by adding the current element to the prefix sum at index i-1 (previous prefix sum), i.e. prefixSum[i] = prefixSum[i-1] + arr[i] . Repeat step c and and calculate the prefix sum at all indices from 1 to n . Get range sum: Once the prefix sum array is constructed, we can get the subarray sum of any range from 0 to n in arr . Use the appropriate range sum formula described earlier for calculating range sum: Range Sum (start, end) = prefixSum[end] - prefixSum[start - 1] or Range Sum (0, end) = prefixSum[end] Want to master coding? Looking to upskill and crack interviews? We suggest you check out these specially designed courses: Udemy Video Tutorials - Available at 95% off System Design Interview Complete Guide Data Structures And Algorithms - A Complete Guide   Learn In-Demand Tech Skills And Stay Ahead Of Others Simulation Let's understand this algorithm with an example. Consider arr = [1, 2, 3, 4, 5, 6] is the given array. We are asked to find the range sum from index 2 to 5 . First we construct the prefix sum array using the formula prefixSum[i]  = prefixSum[i-1]  + arr[i] . After applying this formula for every index from 0  to n , our final prefixSum array for arr will be as shown below: Next use the range sum formula for getting the range sum from 2 to 5: As you can see from above diagram range sum from 2 to 5 is equal to 21, which is the sum of elements at indices 2 to 5, i.e. elements [3, 4, 5, 6]. Below is a pictorial depiction of how the range sum formula works in general: As you can see from the above diagram, when the sum of elements before the start index of a range is subtracted from the sum of all elements till the last range index, this will effectively give us the difference between two sums, which is nothing but the range sum from start to end . This is the intuition behind using this formula for calculating the range sum. Code Go Python Java JavaScript TypeScript C C++ C# PHP Kotlin Swift Ruby Scala Rust Complexity Analysis Time Complexity Constructing prefix sum array: We must traverse every element in the given array arr once in order to construct prefixSum array. Time complexity for this step is O(n) . Getting range sum or subarray sum: Once the prefix sum array is available, we can get the range sum directly using the range sum formula. This takes constant time, so time complexity for this step is O(1) . Overall time complexity: Combining the above two steps, the overall time complexity for getting the range sum/subarray sum using the prefix sum technique is O(n) + O(1) = O(n) . Space Complexity This pattern uses the an additional array prefixSum for storing prefix sums for each index in arr . Hence the space complexity for prefix sum pattern is O(n) . Other Applications of Prefix Sum Apart from range sum range calculation, prefix sum pattern is also used in several other use cases. Few are described below: Finding sum of subarrays. Counting subarrays with specific properties (like subarrays with given sum, subarrays divisible by k etc.). Optimizing sliding window problems. 2D prefix sum problems. Conclusion The prefix sum pattern helps us simplify and optimize a diverse range of coding problems. By pre-computing prefix sums we can bring down the time complexity of problems like range queries, subarray sum problems from quadratic time to linear time. Mastering this pattern is essential for competitive programming and technical interviews. We hope this article has helped you build a solid understanding of the prefix sum pattern. Here are some problems we covered so far on prefix sum pattern: 1991. Find the Middle Index in Array 560. Subarray Sum Equals K In the upcoming articles we will solve several problems using this pattern. Subscribe to Code Recipe and stay tuned for more! Code Recipe Limited Time Offer:   Enjoy a 100% discount on the Code Recipe Membership Plan. Sign up now and get access to exclusive premium content for free. Act fast—offer only available for a limited time - Join now .

Hello Code Recipian! In our previous article we introduced the prefix sum pattern , and as promised, we are back with a solution to problem 1991. Find the Middle Index in Array which uses this pattern. This problem is a direct application of the prefix sum coding pattern discussed in our previous article. If you haven't read it yet, we highly recommend checking it out before continuing with this one. Okay —with that said let's dive into the problem statement! Problem Statement: 1991. Find the Middle Index in Array Given an integer array nums , find the middle index in nums array, middleIndex . Note that you must find the leftmost middle index in nums array. A middleIndex is an index where nums[0] + nums[1] + ... + nums[middleIndex-1] == nums[middleIndex+1]  + nums[middleIndex+2]  + ... + nums[nums.length-1] . For the first element in nums , the left sum is considered 0, and for the last element, the right sum is considered 0. Return the leftmost middleIndex that satisfies this condition, if there is no such index then return -1. Example 1 Input:  nums = [2, 3, -1, 8 , 4] Output:  3 Justification :  The sum of the numbers to the left of index 3 is (2 + 3 + -1 = 4) and the sum of the numbers to the right of index 3 is also 4. Example 2 Input : nums = [2, 1, -1] Output : 0 Justification : The sum of the numbers to the left of index 0 is 0. The sum of the numbers to the right of index 0 (1 + -1 = 0) is also 0. Constraints 1 <= nums.length <= 100 -1000 <= nums[i] <= 1000 Solution To solve this problem, we need to calculate the sum of elements on both sides of each element in nums array. A straight forward way to solve this problem is to use nested loops, but that would result in suboptimal time complexity. Instead, we will use the prefix sum technique, which ensures efficiency in both time and space. Let's see how this works. Algorithm Below is a step-by-step explanation for the working of the algorithm: Calculate total sum: Create an integer variable totalSum and initialize it to 0. Iterate through all elements in nums array and calculate the total sum. Let's store this in totalSum . totalSum will be used in our next step to efficiently calculate the right sum. Find middle index: In this step we calculate left sum and right sum and check if they are equal. Left sum is calculated in each iteration as we traverse through the array, right sum is calculated using mathematical formula: Create an integer variable leftSum  and initialize it to 0. Since we have the total sum from previous step, we can calculate the right sum using the formula: rightSum = totalSum - leftSum - current number Once we have the right sum, compare it with the current left sum and check if they are equal. If leftSum == rightSum , we have found the middle element, immediately return the current index as result. If leftSum != rightSum , update leftSum by adding the current number to it and continue iterating. Middle index not found: If the execution comes out of the 2nd loop without returning, it means the given nums array does not contain a middle index. Therefore return -1 as result. Want to master coding? Looking to upskill and crack interviews? We suggest you check out these specially designed courses: Artificial Intelligence A-Z 2025: Build 7 AI + LLM & ChatGPT Udemy Video Tutorials - Available at 95% off System Design Interview Complete Guide Data Structures And Algorithms - A Complete Guide   Learn In-Demand Tech Skills And Stay Ahead Of Others Simulation Below is a pictorial depiction for the working of the algorithm: Code Go Solution Python Solution Java Solution JavaScript Solution TypeScript Solution C++ Solution C# Solution C Solution PHP Solution Kotlin Solution Swift Solution Ruby Solution Scala Solution Rust Solution Complexity Analysis Time Complexity Calculating total sum: For calculating the total sum we iterate through all elements of nums once. Hence the time complexity for this step is O(n) . Checking if middle element exists: For checking if there exists a middle element in nums array, we use another loop for iterating through all elements. Apart from this all operations inside the loop are constant time operations. Hence the time complexity for this step is O(n) . Overall time complexity: Combining the above time complexities for individual steps, the overall time complexity of this solution is O(n) + O(n) = O(n) . Space Complexity Apart from few variables which use constant space, we do not use any extra space that is a varies with the input size. Hence the overall space complexity of this solution is O(1) . These are some of the problems we've solved using the prefix sum pattern: 560. Subarray Sum Equals K That is all for this article. We will be back with more problems related to prefix sum pattern. Do not miss to check out our other articles in the LeetCode problem solutions series. Code Recipe Limited Time Offer:  Get 100% discount on the Code Recipe Membership Plan. Sign up now and get access to exclusive premium content for free. Hurry—offer only available for a limited time - Join now .

Introduction Singleton Design Pattern is a creational design pattern. Singleton pattern lets you ensure that only one instance of a class (struct in go) is created. This single instance created is called singleton object or singleton instance. Singleton pattern lets you ensure that a class has only one instance, thereby providing a global access to this instance. The singleton pattern usually provides a global method which is responsible for creating and returning this singleton instance. This global method wraps the object creation logic thereby hiding the complexity from the client. The user of this object might not even realize that he is working with a singleton object. When we say singleton object is accessible globally, it is important we make sure that we wont allow clients to modify this global object. Once the singleton object is created the pattern should ensure that it is immutable. Otherwise the client or application may end up seeing an unexpected behaviour while using this object. The singleton pattern ensures that the object is created only once, and once it is created the pattern returns the same object without any modification, no matter how many times the client tries to get the object. To ensure that the singleton object is accessed globally and that it cannot be modified once created, singleton pattern encapsulates the singleton object inside a globally accessible method, also you need to make the instance unexported which guarantees it is not accessible directly outside the package. Use cases where singleton pattern is useful: Database connection object : In case of a database, creating a database connection object is usually an expensive operation since it needs a lot of heavy-lifting to be done in the background. So, ideally what we would want in this case is to create the database connection object once and reuse it across our application rather than creating a new object for each call. This makes singleton pattern an ideal choice for this use case. Logger : Even in case of logging for an application, enabling or disabling logs, changing the severity of logged messages etc needs to be done on a single instance which makes singleton pattern suitable for this case. Implementation As mentioned earlier, we need to provide a global GetInstance() method to our users. The first caller who calls this method creates the singleton instance. For rest of the callers we return the same instance which was created earlier. As simple as it may seem, it is very easy to get the singleton pattern wrong. Lets discuss some of the correct ways to create the singleton pattern in go. In go the singleton pattern can be implemented in two ways mainly: Using mutex locks. Using the Once.Do() method in sync package. Using Mutex Locks One way to implement the singleton pattern in go is to make use of mutex locks. You can find the mutex lock methods ( Lock and Unlock ) in go "sync" package. Below is a implementation using mutex locks: The idea here is simple. During the program execution, the first thread or go routine to call the GetInstance() method acquires the lock and continues execution to the next line of code. After this point no matter how many threads try to call the GetInstance() method, they will be locked at line 13 in code, they wont be allowed to proceed further since the first thread has already acquired the lock. The first thread satisfies " if instance == nil " condition and therefore enters the if block and creates a singleton instance (line 17) and returns it (line 19). Once the first thread returns from GetInstance() method the mutex lock is released and next thread (in order as they are called) acquires the lock. But now onward " if instance == nil " condition is always false since the first thread has already created a singleton instance. Therefore all threads after the first thread simply return from the GetInstance() method without creating a new instance. Thus the GetInstance() method returns a single instance of singleton struct no matter how many times it is called. This approach works fine and does serve its purpose of creating a singleton instance. But there is one slight drawback in the above implementation. Mutex locks can be expensive because it needs to do some bookkeeping in the background to ensure that no more than one thread or go routine acquires lock at a time, among other things. This is especially true when there are multiple threads trying to acquire a lock. In the above implementation, if there are 100 calls to GetInstance() method, all 100 threads will acquire a lock before returning the singleton instance. But we know acquiring a lock after the first thread (after the singleton instance is created) is unnecessary. The purpose of using mutex lock is to ensure that if multiple threads try to access the GetInstance() method at the same time, in parallel, the GetInstance() methods doesn't create multiple instances (multiple copies) of our singleton struct. However, we can modify the above implementation slightly to overcome this drawback. All that we have to do is wrap lines 13-18 within another " instance == nil " check. This way all calls to GetInstance() method that come after the first call doesn't have to acquire a lock, our GetInstance() method can simply return the singleton instance after the outer " instance == nil " check. Below is the modified solution: The first (outer) if statement checks if the thread needs to acquire lock, and the second (inner) if statement tell us if the singleton instance is already created or we need to create it. Want to master coding? Looking to learn new skills and crack interviews? We recommend you to explore these tailor made courses: Udemy Video Tutorials - Available at 95% off System Design Interview Complete Guide Cracking The Coding Interview - Most Preferred Book For Coding Interviews Data Structures And Algorithms - A Complete Guide Learn In-Demand Tech Skills And Stay Ahead Of Others Using "Once.Do()" Method Another way to implement the singleton pattern in golang is by using the Once.Do() method in sync package. The library ensures that the code within once.Do() block is executed only once, this guarantee is implicitly provided by go. Note: To know more about the internal working of Once.Do() method refer this . Below is the implementation using Once.Do(): In this method we place the singleton instance creation code inside the Once.Do() block instead of using the mutex locks. The Once.Do() method also uses mutex locks internally, so it is necessary to use the outer if statement even for this approach. Output We can test both these implementations using the the below code snippet: The above snippet creates 1000 go routines which call the GetInstance() method almost in parallel. You can notice from the below output that both of our solutions print the "Creating a new singleton instance" message only once indicating only one instance of the singleton struct is created even though 1000 goroutines are invoking the GetInstance() method. That is all for this article, thank you for taking your time to read this. If you have any questions or doubts, please let us know in the comments section below, we will be happy to answer you. If you found this article useful, do not forget to subscribe to our website, your support motivates us to bring out more such articles in future (scroll down to the bottom of the page to find the subscription form). You can explore more such amazing articles from code recipe in our blogs section . Code Recipe Limited Time Offer:   Get 100% discount on Code Recipe Membership Plan. Join now and get exclusive access to premium content for free. Hurry! Offer only available for a limited time - Join now . Follow us: YouTube , Facebook , Twitter , LinkedIn , Tumblr , Instagram .